CODEWITHSUNDEEP
haskell
mariop
mariop

Reputation: 3216

Why the cycle function cannot work with empty list?

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?

Upvotes: 17

Views: 1173

Answers (5)

cheecheeo
cheecheeo

Reputation: 682

The intent of cycle as described in the documentation is:

import Data.List.Nonempty
import Data.Stream.Infinite

cycle :: NonEmpty a -> Stream a

The authors of the Prelude use a partial function for passing in an empty list, which is conceptually a type error, similar to head and tail.

If you'd like a cycle that returns [] it's as easy as:

myCycle :: [a] -> [a]
myCycle xs = if null xs then xs else cycle xs

See: semigroups for the definition of NonEmpty and streams for the definition of Stream and a total definition of cycle.

Upvotes: 1

Dan Burton
Dan Burton

Reputation: 53665

Note that as it is currently defined, it is consistent with tail.

tail [] = error ...

cycle is conceptually related to tail. When you cycle a list, that means that you can repeatedly look to its tail and never reach the "end" ([]), because it is a cycle. (See Davorak's image.) In other words, it is always safe to use tail on a cycle'd list, assuming, of course, that it was safe to use cycle on that list in the first place.

I, for one, think it is a perfectly reasonable thing to define.

tail [] = []
cycle [] = []

But you should redefine both cycle and tail for consistency.

Upvotes: 2

Davorak
Davorak

Reputation: 7444

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.

Upvotes: 3

Carl
Carl

Reputation: 27003

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.

Upvotes: 7

ThreeFx
ThreeFx

Reputation: 7350

The problem arises when it comes to accessing elements in the list. A self-defined cycle function operating on a non-empty list has no problems when being accessed but trying to get, for example, the first 3 elements of the cycled empty list results in an infinite loop:

cycle' xs = xs ++ cycle' xs

take 3 (cycle' [1,2]) -- returns [1,2,1]
take 3 (cycle' [])    -- still looping

Upvotes: 3

Related Questions