6 people like it.
Like the snippet!

IRC Jokes

Simple snippet that demonstrates recursively defined discriminated unions, the Y combinator (for encoding recursive functions) and recursive processing of tree-like structures

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 
21: 
22: 
23: 
24: 
25: 
26: 
27: 
28: 
29: 
30: 
31: 
32: 
33: 
34: 
35: 
36: 
37: 
38: 
39: 
40: 
41: 
42: 
43: 
44: 
45:

(*

irc.freenode.org, channel ##fsharp

<LionMadeOfLions> scientists are baffled, though, it will be decades before we
                  begin to understand the lions made of lions

<ninegrid> challenge accepted
*)


type LionMadeOfLions = Lions | Lion of LionMadeOfLions * LionMadeOfLions
let lionMadeOfLions = Lion(Lion(Lion(Lions,Lions),Lions),Lions)

(*
           Lion
          /    \
         Lion  Lions
        /    \
      Lion  Lions
      /   \
    Lions Lions

*)

let rec y f x = f (y f) x
let understand x = printfn "%A" x

let lions (lions : LionMadeOfLions -> LionMadeOfLions) = function
  | Lion (x,y) -> lions x
  | Lions      -> Lions

y (lions >> fun f lion -> understand lion; f lion) lionMadeOfLions

(* output:

> 
Lion (Lion (Lion (Lions,Lions),Lions),Lions)
Lion (Lion (Lions,Lions),Lions)
Lion (Lions,Lions)
Lions
val it : LionMadeOfLions = Lions

*)

union case LionMadeOfLions.Lions: LionMadeOfLions

union case LionMadeOfLions.Lion: LionMadeOfLions * LionMadeOfLions -> LionMadeOfLions

type LionMadeOfLions =
| Lions
| Lion of LionMadeOfLions * LionMadeOfLions

Full name: Script.LionMadeOfLions

val lionMadeOfLions : LionMadeOfLions

Full name: Script.lionMadeOfLions

val y : f:(('a -> 'b) -> 'a -> 'b) -> x:'a -> 'b

Full name: Script.y

val f : (('a -> 'b) -> 'a -> 'b)

val x : 'a

val understand : x:'a -> unit

Full name: Script.understand

val printfn : format:Printf.TextWriterFormat<'T> -> 'T

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.printfn

val lions : lions:(LionMadeOfLions -> LionMadeOfLions) -> _arg1:LionMadeOfLions -> LionMadeOfLions

Full name: Script.lions

val lions : (LionMadeOfLions -> LionMadeOfLions)

val x : LionMadeOfLions

val y : LionMadeOfLions

val f : (LionMadeOfLions -> LionMadeOfLions)

val lion : LionMadeOfLions

Next Version Raw view Test code New version

More information

Link:	http://fssnip.net/3V
Posted:	13 years ago
Author:	Daniel Jackson
Tags:	recursion , y-combinator , discriminated unions