[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.+.
Adding ~ to
(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))
--------
More information about the Haskell-Cafe
mailing list