How to detect finite/infinite lists?
Extremely-newbie questions: Is there any way to know if a list is finite or infinite, other than doing: length l and waiting forever? :) I ask because I was learning Haskell by writing some pretty naive implementation of surreal numbers, where I used lists for left and right surreal sets, and I wanted to do some operations on the sets (like finding the maximum/minimum), but obviously just on finite sets. I vaguely suspect the answer is going to be: "No, because lists are lazy (at least when they are :) and there's no general way to know beforehand how many elements they're going to have". But still, if I write x = [1..5] the compiler knows pretty well x is not going to grow any new member... (Unrelated) Is there any standard function to do: interleave [] _ = [] interleave _ [] = [] interleave (x:xs) (y:ys) = x : y : interleave xs ys It's pretty easy to implement as shown or via zipWith, but given that Haskell 98 already includes some "basic" functions (like cycle, iterate, etc.) I wonder if I've missed this one somehow. Thanks, /L/e/k/t/u
On Thu, 18 Sep 2003, Juanma Barranquero wrote:
Extremely-newbie questions:
Is there any way to know if a list is finite or infinite, other than doing:
length l
and waiting forever? :)
I ask because I was learning Haskell by writing some pretty naive implementation of surreal numbers, where I used lists for left and right surreal sets, and I wanted to do some operations on the sets (like finding the maximum/minimum), but obviously just on finite sets.
I vaguely suspect the answer is going to be: "No, because lists are lazy (at least when they are :) and there's no general way to know beforehand how many elements they're going to have". But still, if I write
x = [1..5]
the compiler knows pretty well x is not going to grow any new member...
Well, it's easy to tell that a list is finite by running length and having it terminate. This is obviously equivalent to the halting problem so you can't really expect anything better in general. Why do you need to test whether lists are infinite? If your lists are being generated from finite descriptions maybe you could use a data structure that records the descriptions. For example, rather than defining l = [1..]++[2,3..7] you could define data EnumList = EnumFromBy Integer Integer | EnumFromToBy Int Int Int | Append EnumList EnumList l = EnumFromBy 1 1 `Append` EnumFromToBy 2 1 7 then to test whether a list is infinite you can write infinite (EnumFromBy _ _) = True infinite (EnumFromToBy a delta b) = compare a delta == compare a b infinite (Append l1 l2) = infinite l1 && infinite l2 Of course this only works if it is computable whether a description gives a finite list.
(Unrelated) Is there any standard function to do:
interleave [] _ = [] interleave _ [] = [] interleave (x:xs) (y:ys) = x : y : interleave xs ys
It's pretty easy to implement as shown or via zipWith, but given that Haskell 98 already includes some "basic" functions (like cycle, iterate, etc.) I wonder if I've missed this one somehow.
Thanks,
Not as far as I know. The standard List module doesn't define anything like that and Data.List doesn't define anything like that. What do you want to use it for? If you are looking for strict alternation you should use this defintion. If you want a nondeterministic merge as elements are computed, look at mergeIO in Control.Concurrent in the GHC libraries. Brandon
On Thu, 18 Sep 2003 12:28:41 -0700 (PDT), Brandon Michael Moore
This is obviously equivalent to the halting problem so you can't really expect anything better in general.
No, obviously not in general. But a human wouldn't sweat to say that [1..5] is finite and [1..] infinite. As I have no idea how the compiler is implemented, I don't know if it knows whether what it has on its hands is a fixed, short-length list (like [1..5], which I imagine the compiler would perhaps pre-generate instead of lazy-evaluating it), or one which in fact comes from some kind of generator function(s).
Why do you need to test whether lists are infinite?
I had something like: data Surreal = Surreal { leftSet::[Surreal], rightSet::[Surreal] } where leftSet and rightSet could potentially contain infinite lists of Surreals. Knowing that both sets are finite would allow to simplify some numbers (in surreal numbers, it is the case that {-1|1} = {|}, for example, and being able to simplify {-1|1} to {|} can help, specially when trying to show/print the numbers).
If your lists are being generated from finite descriptions maybe you could use a data structure that records the descriptions.
Yes, I think you're right.
What do you want to use it for? If you are looking for strict alternation you should use this defintion.
Yes, strict alternation (output, in fact). I have lists of columns and lists of separators and I interleave them while generating a line of output. Thanks, /L/e/k/t/u
[[Sent to Haskell-café, and to comp.lang.fun]]
If you look at some Web sites (Mathworld, the site of John Baez - a known
spec. in algebraic methods in physics), or into some books on differential
geometry, you might easily find something which is called pullback or
pull-back.
Actually, it is the construction of a dual, whose meaning can be distilled
and implemented in Haskell as follows. The stuff is very old, and very well
known.
Suppose you have two domains X and Y. A function F : X -> Y. The form (F x)
gives some y.
You have also a functor which constructs the dual spaces, X* and Y* - spaces
of functionals over X or Y. A function g belongs to Y* if g : Y -> Z (some
Z, let's keep one space like this).
Now, I can easily construct a dual to F, the function F* : Y* -> X* by
(F* g) x = g (F x)
and this mapping is called pullback...
While there is nothing wrong with that, and in Haskell one may easily
write the 'star' generator
(star f) g x = g (f x)
or
star = flip (.)
... I have absolutely no clue why this is called a pullback. Moreover, in
the incriminated diff. geom. books, its inverse is *not* called pushout,
but push-forward. Anyway, I cannot draw any pullback diagram from that.
The closest thing I found is the construction in Asperti & Longo,
where a F in C[A,B] induces F* : C!B -> C!A where the exclam.
sign is \downarrow, the "category over ...".
The diagram is there, a 9-edge prism, but - in my eyes - is quite
different from what one can get from this "contravariant composition"
above. But my eyes are not much better than my ears, so...
I sent this question to a few gurus, and the answers are not conclusive,
although it seems that this *is* a terminologic confusion.
Vincent Danos
it really doesn't look like a categorical pullback and it might well be a "pull-back" only in the sense that if if F:A->B is a linear map say and f is a linear form on B, then F*(f) is a linear form on A defined as F*(f)(a)=f(b=F(a)) so one can "pull back" (linearly of course!) linear forms on B to linear forms on A "back" refers to the direction of F, i'd say.
================================== Does anybody have a different (or any!) idea about that? Thank you in advance for helping me to solve my homework. Jerzy Karczmarczuk Caen, France
On Thu, 18 Sep 2003 20:16:33 +0200
Juanma Barranquero
Extremely-newbie questions:
Is there any way to know if a list is finite or infinite, other than doing:
length l
and waiting forever? :)
In Haskell 98, no. With a slightly impure extension (observable sharing) sometimes but in general, no. The only infinity you need to recognize is omega and that's just an infinite (cyclic) list of whatevers. So you -could- use observable sharing for this, but there isn't much point to it, just use a data structure that says, "an infinity of x". The simplest thing I would think of is to follow the arithmetic operation exactly. data SN = Zero | Up | Down | SN :+: SN | SN :*: SN | SN :^: SN | Omega SN omega = Omega Up iota = Up :+: Omega Down twoThirds = Omega (Up :+: Down) twoOmega = Omega Up :+: Omega Up omegaSquared = Omega Up :*: Omega Up omegaToTheOmega = Omega Up :^: Omega Up
On Thu, 18 Sep 2003 15:53:12 -0400, Derek Elkins
In Haskell 98, no. With a slightly impure extension (observable sharing) sometimes but in general, no.
Interesting.
just use a data structure that says, "an infinity of x". The simplest thing I would think of is to follow the arithmetic operation exactly.
data SN = Zero | Up | Down | SN :+: SN | SN :*: SN | SN :^: SN | Omega SN
:) Thanks, /L/e/k/t/u
participants (4)
-
Brandon Michael Moore -
Derek Elkins -
Jerzy Karczmarczuk -
Juanma Barranquero