Let's consider a simple function that takes a list and produces a sequence of the reversed list.

```
let rec reverse l =
seq { match l with
|h::t -> yield! reverse t
yield h
|[] -> yield! Seq.empty
}
```

Now let's try to count the number of elements of a very large sequence.
```
let ls = Seq.to_list (seq {for i in 1..10000000 -> i})
Seq.fold (fun acc _ -> acc+1) 1 (reverse ls)
```

And here, what happen? We get a stack overflow.
Maybe the beginning of an explanation lies in the definition of reverse.
Looking at it, we can see that the recursive call

```
yield! reverse t
```

appears before yielding the current head of the list. So we have a recursive call that is not in tail position.
That explains the stack overflow.

A solution is to use continuation passing style to move the recursive call to a tail position.```
let reverse l =
let k0 () = Seq.empty
let rec proc l kc =
seq { match l with
|h::t -> let kc' () = seq { yield h
yield! kc()
}
yield! (proc t kc')
|[] -> yield! kc ()
}
proc l k0
```

Now it works!
## 1 comment:

Storing data inside of a function is pretty neat. Brian goes into some good catamorphism examples using it. In this case kc doesn't have to be a function and the sequence can be passed as a parameter since the new sequence object itself is storing the extra data.

Post a Comment