将 Haskell 代码转换为 Python 或伪代码

Question

我正在研究一种算法。但是作者提供的haskell代码我不是很清楚，所以我需要你们的帮助。我认为代码可以分为两部分。

> type LFT = (Integer, Integer, Integer, Integer)
>
> extr :: LFT -> Integer -> Rational
> extr (q,r,s,t) x = ((fromInteger q) * x + (fromInteger r)) / ((fromInteger s) * x + (fromInteger t))
>
> unit :: LFT
> unit = (1,0,0,1)
>
> comp :: LFT -> LFT -> LFT
> comp (q,r,s,t) (u,v,w,x) = (q*u+r*w,q*v+r*x,s*u+t*w,s*v+t*x)

这里，很明显，一个叫做LFT的类型（可能是Python中的元组）和三个叫做的函数extr unit comp被定义了。 然而，接下来的部分让我很困惑：

> pi = stream next safe prod cons init lfts where
>   init = unit
>   lfts = [(k, 4*k+2, 0, 2*k+1) | k<-[1..]]
>   next z = floor (extr z 3)
>   safe z n = (n == floor (extr z 4))
>   prod z n = comp (10, -10*n, 0, 1) z
>   cons z z’ = comp z z’

我相信lfts是一个生成器，但我无法理解此代码中的循环是如何执行的，而且我对 Haskell 了解不多。你能帮我把这个转换成 Python 或伪代码吗？

Answer 1

首先lfts是一个无限列表。您可以使用itertools.count以下方法编写非常相似的代码：

from itertools import count

# count(1) is "equivalent2 to [1..]
lfts = ((k, 4*k+2, 0, 2*k+1) for k in count(1))

现在代码的重要事情是调用stream它是一个“执行循环”的函数。该函数在文章中定义为：

> stream :: (b->c) -> (b->c->Bool) -> (b->c->b) -> (b->a->b) ->
>           b -> [a] -> [c]
> stream next safe prod cons z (x:xs)
>   = if   safe z y
>     then y : stream next safe prod cons (prod z y) (x:xs)
>     else stream next safe prod cons (cons z x) xs
>       where y = next z

的想法stream是：

• 最后一个参数 ( x:xs) 是一个（无限）输入列表（类型[a]）
• 倒数第二个参数 ( z) 是某种形式的状态（类型b）

• 其他四个参数是操作输入和状态的函数：

  • 该next函数接受一个状态并产生一个输出 ( y)。
  • 该safe函数检查是否y应在输出中添加
  • 该prod函数产生新的状态
  • cons当y值未添加到输出时调用该函数，并用于从输入值生成新状态x。

您可以重现这样的功能：

import itertools as it

def stream(nxt, safe, prod, cons, state, inputs):
    x = next(inputs)   # obtain x
    # xs = inputs
    y = nxt(state)
    if safe(state, y):
        yield y
        inputs = it.chain([x], inputs)   # put x back in the input
        yield from stream(nxt, safe, prod, cons, prod(state, y), inputs)
    else:
        yield from stream(nxt, safe, prod, cons, cons(state, x), inputs)

所以基本上它所做的是从某个状态开始产生一些值。当它达到某个条件时，它会消耗一个输入值来产生一个新状态并产生更多值，当它再次停止时，它将使用另一个输入值再次产生一个新状态，等等。无穷无尽。

请注意，上述实现的性能非常差。最好避免在 python 中递归，所以我会使用：

def stream(nxt, safe, prod, cons, state, inputs):
    while True:
        x = next(inputs)   # obtain x
        # xs = inputs
        y = nxt(state)
        if safe(state, y):
            yield y
            inputs = it.chain([x], inputs)   # put x back in the input
            state = prod(state, y)
        else:
            state = cons(state, x)