将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或伪代码吗？

- Page David

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

< p > 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)

- Bakuriu

Answer 2

lfts 实际上是一个（惰性）生成器，与以下代码更或多或少等价：

def lfts () :
    k = 1
    while True :
        yield (k,4*k+2,0,2*k+1)
        k += 1

这是因为[1..]是一个从1开始递增的无限列表。现在，k <- [1..]表示每次选择列表中的下一个值作为k，并且你会yield列表推导式左边的内容。

因此，它是一个生成器，将生成一个无限列表，因此您不能简单地调用list()或len()。

---

你也可以使用来自 itertools 的 count 来生成一行代码：

((k,4*k+2,0,2*k+1) for k in itertools.count(1))

你可以使用 itertools.islice 来获取前五个元素：

>>> list(itertools.islice(((k,4*k+2,0,2*k+1) for k in itertools.count(1)), 0, 5))
[(1, 6, 0, 3), (2, 10, 0, 5), (3, 14, 0, 7), (4, 18, 0, 9), (5, 22, 0, 11)]

由于生成器可以一直生成元素，因此您可以轻松地获取任意数量的元素（超过五个，但二十个显然也是一个选项）。

- Willem Van Onsem

---

这很清楚，但我不明白这段代码中的迭代是如何执行的。你能解释一下吗？ - Page David

@DavidPage：在Python中，你可以使用yield关键字来描述一个生成器。Python将其视为连续体：如果你要求第一个元素，它将执行直到遇到第一个yield语句，并暂停方法的执行。如果之后再请求下一个元素，它会再次执行并在产生第二个元素后暂停，依此类推。 - Willem Van Onsem