Convert a Haskell code to Python or pseudocode

Question

I am working on an algorithm. But I am not very clear on the haskell code provide by the author, so I need you guys' help. The codes can split into two parts, I think.

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

Here, very clearly, a type called LFT (may be a tuple in Python) and three function called extr unit comp be defined.However, the next part puzzled me a lot:

> 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’

I believe lfts is a generator but I am failed to understand how the loop performed in this code and I do not know much about the Haskell. Can you help me convert this one to Python or a pseudocode?

Answer 1

First of all the lfts is an infinite list. You can write very similar code using 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))

Now the important thing of the code is the call to stream which is a function that "performs the loop". That function is defined in the article as:

> 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

The idea of stream is that:

• The last argument (x:xs) is an (infinite) input list (of type [a])
• The one-to-last argument (z) is some form of state (of type b)

• The other four arguments are functions that manipulate inputs and state:

  • The next function takes a state and produces an output (y).
  • The safe function checks whether y should be added in the output or not
  • The prod function produces the new state
  • The cons function is called when the y value is not added to the output and is used to produce the new state from the input value x.

You can reproduce such a function as:

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)

So basically what this does is that it yields some values starting from a certain state. When it reaches a certain condition it consume an input value to produce a new state and yield more values, when it stops again it will use an other input value to produce a new state again etc. Ad infinitum.

Note that the above implementation will have really bad performance. It's better to avoid recursion in python so I'd use:

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)

Answer 2

lfts is indeed a (lazy) generator which is more or less equivalent to:

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

This is because [1..] is an infinite list of incrementing integers starting from 1. Now k <- [1..] means that k each time picks the next value in the list, and you yield the thing at the left of the list comprehension.

It is thus a generator that will generate an infinite list, therefore you cannot simply call list() or len() onto it.

---

You can also use count from itertools to produce a oneliner:

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

You can then take for instance the first five elements using 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)]

Since the generator can generate elements until the end of times, you can easily take an arbitrary amount of elements (above five, but twenty is evidently an option as well).