[Haskell-cafe] Recursion problem in infinite list model

Hans Aberg haberg at math.su.se
Fri Mar 28 08:40:49 EDT 2008

```On 28 Mar 2008, at 03:03, Ryan Ingram wrote:
> Another way to defer the evaluation of the second argument of (-+)
> is like this:
>
> (-+) :: a -> List a -> List a
> x -+ y = List(f) where
>   f 0 = x
>   f k = case y of List g -> g (k-1)
>
> This is exactly what the lazy pattern will do at compile-time.  Does
> this give you a better understanding of how lazy patterns work and why
> they fix the problem?

I can isolate the problem with the addition in the code below, where
I have defined a type Natural just in order to introduce a user
defined operator. - For ordinals, it is more complicated. Then
h (list 6)
only printouts "[N 6,", after which it gets stuck in the Natural.+.
(N x) + (N y)
does not help, nor other variations. But replacing Natural with
integer, produces the normal infinite list printout. So it must be
here it is stuck.

Hans

--------
infix 5  :+

data Natural = N Integer
deriving (Eq, Show)

instance Num Natural where
fromInteger x = N x
abs x = x
signum 0 = 0
signum _ = 1
(N x) + (N y) = N(x + y)

data List a = (Natural->a) :+ Natural

instance Show a => Show (List a) where
show (f :+ _) = "[" ++ show (f(0)) ++
concat ["," ++ show (f(N (toInteger i)))| i<-[1..]] ++ "]"

list :: Natural -> List Natural
list x = (\z -> x+z) :+ 0

(-+) :: a -> List a -> List a
x -+ ~(y :+ q) = f:+(1+q) where
f 0 = x
f k = y(k-1)

first :: List a -> a
first (f :+ _) = f 0

rest :: List a -> List a
rest (y :+ _) = f :+ 0 where
f k = y(k+1)

h :: List a -> List a
h x = (-+) (first x) (h (rest x))
--------

```