[Haskell-cafe] The values of infinite lists
fis at wiwi.hu-berlin.de
Wed May 10 03:51:42 EDT 2006
On Wed, May 10, 2006 at 02:00:20PM +0900, Deokhwan Kim wrote:
> To: haskell-cafe at haskell.org
> From: Deokhwan Kim <dk at ropas.snu.ac.kr>
> Date: Wed, 10 May 2006 14:00:20 +0900
> Subject: [Haskell-cafe] The values of infinite lists
> Are the values of infinite lists _|_ (bottom)?
> In section 1.3, the Haskell 98 report said as follows:
> Errors in Haskell are semantically equivalent to _|_. Technically,
> they are not distinguishable from nontermination, so the language
> includes no mechanism for detecting or acting upon errors.
type theoreticians talk like that ;-).
this paragraph is more about the "error" function than about infinite
data structures. it means that whenever you trigger an "error ..."
line, you make the program non-terminating, just like if you try to
access the last element of an infinite list. the program still *ends*
with an error message (notifying you that it won't *terminate*)
because it is nice and it knows you don't like to wait forever. (-:
> Therefore, the value of the following infinity is _|_. Right?
> data Nat = Zero | Succ Nat
> infinity = Succ infinity
same as with lists: as long as you don't get lost in an infinitely
distant point in the data structure, you are fine: you can do this
ghci> case infinity of Succ _ -> "not there yet."; Zero -> "the end."
ghci> take 1000 [1..]
actually one of the things that i still find most amazing about
haskell is that i can express so many algorithms by starting from the
declaration of an infinite data structure and then traversing a finite
part of it. the king paper on graph algorithms in haskell has some
nice examples on this, too.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Size: 189 bytes
Desc: Digital signature
Url : http://www.haskell.org//pipermail/haskell-cafe/attachments/20060510/f45e701f/attachment.bin
More information about the Haskell-Cafe