[Haskell-cafe] Recursion problem in infinite list model

[Hans Aberg]

On 27 Mar 2008, at 17:51, Luke Palmer wrote:

> By your naming, am I correct in assuming that you're implementing
> transfinite lists?
> If so, cool!

Yes, it is an old idea I brought up now. If list length is written  
also for infinite lists, then concatenated lists get indexed by the  
sum of their ordinals (and length too). So length x does not cause  
non-termination if x is an infinite list, but a value. In addition,  
one needs to restrict to singly linked lists; a list is essentially a  
cashed lazy function.

I wrote a class Ordinal for ordinals below epsilon_0, which are the  
ones generated by the first uncountable ordinal (the set of natural  
numbers), and ordinal sum, product and exponentiation, which can be  
represented explicitly using CNF (Cantor's normal form). These are  
not large in mathematical terms, but in computers, I think they will  
suffice a long go.

I haven't debugged it yet. But if somebody is interested, just let me  
know. I think Haskell should have such a module, worked up by  
computer programmers, who surely can do a better job than me :-).  
Small ordinal infinities arise naturally when one has say orders f  
floating windows, or and TeX has (I think) orders of stretchability.

>> The reason I used a "data" construct was that I include the size of
>>  the list, excluded in order to keep the example as simple as  
>> possible:
>>    data List a = List(Ordinal -> a, Ordinal)
>
> This could still be a newtype, because of the tuple you used here.  A
> more standard
> way to do this would be:
>
>     data List a = List (Ordinal -> a) Ordinal
>
> Or a record so you could name them.

Thank you. I tend to favor tuplet notation because the are more  
methematical-like, though I have noticed, it is somewhat cumbersome  
in Haskell pattern matching.

>>  In addition, there seems to be no way to choose default value for a
>>  given (non-empty) type in Haskell, so I wrote it
>>    data List a = Empty | List(Ordinal -> a, Ordinal)
>>  Here, if a type T has a default element t, I can represent the empty
>>  list by
>>    List(\_ -> t, 0)
>>  making the constructor "Empty" redundant.
>
> You could use 'undefined', which has value _|_  (if you're sure that
> it will never
> be used).
>
>   List (const undefined) 0
>
> Or even:
>
>   List undefined 0
>
> Which are almost, but not quite, identical.  (Many argue they  
> should be)

I think I need just something that can be plugged into the function  
spot when length is 0.

   Hans Aberg