Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Why the cycle function cannot work with empty list?

Tags:

haskell

I used the function cycle in some of my projects and today I discovered it isn't a total function, as shown by this GHCI example:

λ> Data.List.cycle []
*** Exception: Prelude.cycle: empty list

I know that Haskells tries to use total functions (except for the fundamental functions head and tail) and I'm not entirely sure of why cycle is not one of them. In my mind, the cycle of the empty list is the empty list and I don't see problems with this. Why cycle for empty lists throws an error?

EDIT: Based on the first answers, I think my idea is not completely clear: I don't want cycle [] to be a computation that never ends. On contrary, I think cycle [] should be the:

cycle :: [a] -> [a]
cycle [] = []
cycle xs = xs ++ cycle xs

The [] is the cycle [] because all the operations do exactly what I except. For instance, take 3 [] is [] and thus take 3 (cycle []) could be []. What's the problem with this solution?

like image 829
mariop Avatar asked Jun 14 '14 18:06

mariop


2 Answers

cycle is actually defined as returning an infinite list for all input. If it attempted to do that naively with an empty input, it would sit in an infinite loop. The error condition is slightly more informative with the same denotational semantics.

Edit:

Since people don't seem to understand what I mean when I say that empty output is bad, consider this simple function:

labelElements :: [a] -> [b] -> [(a, b)]
labelElements labels elements = zip (cycle labels) elements

It's nice and simple, with an obvious error condition when the list of labels is empty. If cycle returned an empty list on empty input, it'd make labelElements silently propogate that bug to its output. At the moment, it screams and yells that you messed up instead. One of these is far better than the other.

like image 190
Carl Avatar answered Oct 14 '22 12:10

Carl


I do not have any special insight into the mind(s) of the people who implemented the cycle function.

The prelude has the following to say about cycle:

cycle ties a finite list into a circular one, or equivalently, the infinite repetition of the original list. It is the identity on infinite lists.

Traditionally when you think of a circularly linked list, wiki entry you have: Screenshot from wiki

How would I express a circular empty list? A pointer going to itself? But even that does not fit.

My best explanation is that circular lists are not normal lists. They are different beasts with different semantics. Just like head is really only full defined on non-empty empty list because there is no first element of an empty list, cycle is only fully defined on non-empty lists because there is no empty circular linked list.

like image 39
Davorak Avatar answered Oct 14 '22 13:10

Davorak