3 people like it.

Appending Two Lists Based on A Discriminated Union Type Using Continuation

Lists are pointers to the head of list. It can be defined by a discriminated union type. Using continuation can do a tail-recursion version of appending two lists.

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 

type ImmutableList<'T> = 
  | Empty 
  | Cons of 'T * ImmutableList<'T>

let append lst1 lst2 = 
  let rec appendCont cont = function
    | Empty -> cont lst2
    | Cons(h,t) -> appendCont (fun accList -> cont(Cons(h,accList))) t
  appendCont (fun x -> x) lst1

let res = append (Cons(1,Cons(2,Empty))) (Cons(3,Cons(4,Empty)))

(*
type ImmutableList<'T> =
| Empty
| Cons of 'T * ImmutableList<'T>
val append : ImmutableList<'a> -> ImmutableList<'a> -> ImmutableList<'a>
val res : ImmutableList<int> = Cons (1,Cons (2,Cons (3,Cons (4,Empty))))
*)
union case ImmutableList.Empty: ImmutableList<'T>
union case ImmutableList.Cons: 'T * ImmutableList<'T> -> ImmutableList<'T>
type ImmutableList<'T> =
  | Empty
  | Cons of 'T * ImmutableList<'T>

Full name: Script.ImmutableList<_>
val append : lst1:ImmutableList<'a> -> lst2:ImmutableList<'a> -> ImmutableList<'a>

Full name: Script.append
val lst1 : ImmutableList<'a>
val lst2 : ImmutableList<'a>
val appendCont : ((ImmutableList<'a> -> 'b) -> ImmutableList<'a> -> 'b)
val cont : (ImmutableList<'a> -> 'b)
val h : 'a
val t : ImmutableList<'a>
val accList : ImmutableList<'a>
val x : ImmutableList<'a>
val res : ImmutableList<int>

Full name: Script.res
Raw view Test code New version

More information

Link:http://fssnip.net/e6
Posted:12 years ago
Author:Joel Huang
Tags: list , continuation , discriminated union type

This web site is created using F# and Suave web server. It is hosted on Azure and the source code is on GitHub. Contributions are welcome!

The first version of fssnip.net has been created by @tomaspetricek back in 2010. This web site is a new, open-source and contribution-friendly version.