Learning OCaml and Lazy Evaluation
Lazy evaluation is a cool concept that delays computations until they’re actually needed, saving resources and time. OCaml is great for this, but TypeScript and Go can do it too in their own ways.
OCaml Example
OCaml uses lazy streams to generate Fibonacci numbers:
type 'a stream = Cons of 'a * 'a stream Lazy.t
let rec fibs a b =
Cons (a, lazy (fibs b (a + b)))
let rec take n (Cons (x, xs)) =
if n <= 0 then []
else x :: take (n - 1) (Lazy.force xs)
let () =
fibs 0 1
|> take 10
|> List.iter (Printf.printf "%d, ")
TypeScript Example
TypeScript uses generator functions for lazy evaluation:
function* fibonacci(a: number, b: number): Generator<number> {
while (true) {
yield a;
[a, b] = [b, a + b];
}
}
function take<T>(gen: Generator<T>, n: number): T[] {
const result: T[] = [];
for (let i = 0; i < n; i++) {
const { value, done } = gen.next();
if (done) break;
result.push(value);
}
return result;
}
const fibGen = fibonacci(0, 1);
const first10Fibs = take(fibGen, 10);
console.log(`First 10 Fibonacci numbers: ${first10Fibs.join(", ")}`);
Go Example
Now, Go doesn’t have generators or built in Lazy module but we could achieve the same result with using a channel or implementing a custom recursive type that returns the same type.
Here’s a implementation with channels. We use the same kind of generator that we used in Typescript example:
package main
import (
"fmt"
)
func fibonacci(done <-chan struct{}) <-chan int {
ch := make(chan int)
go func() {
defer close(ch)
a, b := 0, 1
for {
select {
case ch <- a:
a, b = b, a+b
case <-done:
return
}
}
}()
return ch
}
func take(n int, ch <-chan int, done chan<- struct{}) []int {
result := make([]int, 0, n)
for i := 0; i < n; i++ {
val, ok := <-ch
if !ok {
break
}
result = append(result, val)
}
close(done)
return result
}
func main() {
done := make(chan struct{})
fibStream := fibonacci(done)
first10Fibs := take(10, fibStream, done)
for _, v := range first10Fibs {
fmt.Printf("%d, ", v)
}
}
And here’s the one that takes advantage of recursive type and callback to simulate lazy evaluation:
package main
import (
"fmt"
)
type Stream struct {
value int
next func() Stream
}
func fibonacci(a, b int) Stream {
return Stream{
value: a,
next: func() Stream {
return fibonacci(b, a+b)
},
}
}
func take(n int, s Stream) []int {
result := make([]int, 0, n)
for i := 0; i < n; i++ {
result = append(result, s.value)
s = s.next()
}
return result
}
func main() {
fibStream := fibonacci(0, 1)
first10Fibs := take(10, fibStream)
for _, v := range first10Fibs {
fmt.Printf("%d, ", v)
}
}
I just wanted to understand how the same program would look like in the languages I already know(Typescript and Golang). I think the Ocaml’s implementation is elgant and terse. Javascript is cool while Golang’s implementation is probably the most readable and simpler.