用无限序列来生成Fibonacci（的实现）

之前在学Haskell的时候碰到过一段这样的实现：

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

感觉很优雅，主要是因为用到无限序列自己来定义自己，然后就等于把 fib 的定义直译一遍，就得到了对应的函数了（

然后就一直念念不忘是不是可以在命令式里面搞这个。

现在既然有了 Lazy 和 Stream 这两个工具（这里的 Stream 只是一个可以无穷延伸下去的序列，和 Java 上的 Stream 是两回事），就试试开搞吧。需要实现的其实只是一个 zipWith 而已。不过首先实现一个 zip 试试。

// 在 Stream<A> 类里
fun <B> zip(os: Stream<B>): Stream<Pair<A, B>> = when (val ax = this) {
    is Stream.Empty -> Empty
    is Stream.Cons -> when (val bx = os) {
        is Stream.Empty -> Empty
        is Stream.Cons ->
            Cons(ax.hd.flatMap { a -> bx.hd.flatMap { b -> Lazy { a to b } } },
                Lazy { ax.tl().zip(bx.tl()) })
    }
}

因为 kt 里面木有对 Tuple 的模式匹配所以看起来显得啰嗦了一点，不过基本思路大概是这样的：

• 如果其中一个 Stream 是空的，返回一个空 Stream

• 如果不是空的，就先取出左边的第一个元素，然后把剩下的和右边的喂给这个函数自己，一直递归下去。

  这里的 Stream 里面每一个属性都是个 Lazy，所以提取实际的 A 和 B 元素麻烦了点。好在 Lazy 本身也是一个 Monad，用 >>= 就可以把 Lazy 串接起来最后返回一个提取的值的结合的 Lazy 了。

随便试一下，看起来能跑。那就实现 zipWith 吧，和 zip 的实现几乎相同，只是 apply 了个函数进去而已。

fun <B, C> zipWith(os: Stream<B>, f: (A, B) -> C): Stream<C> = when (val ax = this) {
    is Stream.Empty -> Empty
    is Stream.Cons -> when (val bx = os) {
        is Stream.Empty -> Empty
        is Stream.Cons ->
            Cons(ax.hd.flatMap { a -> bx.hd.flatMap { b -> Lazy { f(a, b)  } } },
                Lazy { ax.tl().zipWith(bx.tl(), f) })
    }
}

然后 Stream.tail() 返回的是个 Result，要想直接用的话还要在 Result 上开个洞，加个 unsafeGet() 来提取出里面的值。当然，这样是不安全的。

接下来就可以写函数了：

var fib: Stream<Long> = Stream.Empty
fib = Stream.Cons(Lazy { 0L }, Lazy { Stream.Cons(Lazy { 1L },
    Lazy { fibb.zipWith(fibb.tail().unsafeGet()) { x, y -> x + y } }) })
fib.takeAtMost(80).toList().forEach { println(it) }

这里一开始的写法是在 var fib 定义的地方直接写了个 [0, 1, Nil] 进去，结果因为有个 Nil 所以串接后的 Stream 永远停在 Nil 那里了。所以还是要把 0 和 1 inline 进去。不过如果直接写一行 val fib 的话会在右边提示找不到变量，所以得写两行。

也许可以先写个 [0, 1, Nil] 然后 take(2) ？

总的来说看起来啰嗦了不少不过基本上思路保持了一致，还是不错的。

不过其实有了 Stream，Fibonacci 还可以用别的方式来实现，比如说使用 iterate() 或者 unfold() 函数。

其中 iterate() 的用法是给定一个类型为 A 的种子和一个类型为 (A) -> A 的变换函数，每一步生成一个值，并且以当前值作为下一步的种子。利用 iterate() 写的 fibs 看起来似乎更直观一点？

val fibs: Stream<BigInteger>
    get() = Stream.iterate(BigInteger.ONE to BigInteger.ONE) 
                { (x, y) -> y to (x + y) }.map { it.first }

而 unfold() 则是给定一个类型为 S 的种子和一个类型为 (S) -> Result<Pair<A, S>> 的变换函数，每一步生成一个 A 类型的值压进 Stream 里并且把得到的 S 值传给下一步，如果 f 不再能生成任何值了，那就返回个 Empty。其实就是 fold 的逆操作了（

val fibsUnfold: Stream<BigInteger>
    get() = Stream.unfold(BigInteger.ONE to BigInteger.ONE)
    { (x, y) ->
        Result(x to (y to (x + y)))
    }

感觉用 unfold() 的写法不是那么直观了。

总之大约就是这样。