用无限序列来生成Fibonacci(的实现)

用无限序列来生成Fibonacci(的实现)

八月 23, 2021

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

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

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

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

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

1
2
3
4
5
6
7
8
9
10
// 在 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,所以提取实际的 AB 元素麻烦了点。好在 Lazy 本身也是一个 Monad,用 >>= 就可以把 Lazy 串接起来最后返回一个提取的值的结合的 Lazy 了。

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

1
2
3
4
5
6
7
8
9
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() 来提取出里面的值。当然,这样是不安全的。

接下来就可以写函数了:

1
2
3
4
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 看起来似乎更直观一点?

1
2
3
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 的逆操作了(

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

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

总之大约就是这样。