6 people like it.

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

More information

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