Would the ability to detect cyclic lists in Haskell break any properties of the language?

Question

In Haskell, some lists are cyclic:

ones = 1 : ones

Others are not:

nums = [1..]

And then there are things like this:

more_ones = f 1 where f x = x : f x

This denotes the same value as ones, and certainly that value is a repeating sequence. But whether it's represented in memory as a cyclic data structure is doubtful. (An implementation could do so, but this answer explains that "it's unlikely that this will happen in practice".)

Suppose we take a Haskell implementation and hack into it a built-in function isCycle :: [a] -> Bool that examines the structure of the in-memory representation of the argument. It returns True if the list is physically cyclic and False if the argument is of finite length. Otherwise, it will fail to terminate. (I imagine "hacking it in" because it's impossible to write that function in Haskell.)

Would the existence of this function break any interesting properties of the language?

Well, you suddenly can return different values for the same inputs: `f x = if isCycle x then 1 else 2`. This would return `1` or `2` for the value `ones` depending on how you build that same list. This seems pretty big a breakage considering that one of the most obvious advantages of functional languages is that a function will always return the same result if given the same values in input... — Bakuriu, May 16 '15 at 07:29
This is only ever considered acceptable when constrained to `IO`. You can write `isCycle :: [a] -> IO Bool` in terms of an explicit structure of the graph of a list obtained from [data-reify](https://hackage.haskell.org/package/data-reify) which internally uses [`StableName`s](http://hackage.haskell.org/packages/archive/base/latest/doc/html/System-Mem-StableName.html#t:StableName). If you look too hard at memory with `IO` you can do absolutely evil things, like [break the purity of pure functions without resorting to anything `unsafe`](http://stackoverflow.com/a/28701687/414413). — Cirdec, May 16 '15 at 07:59
Checking if a list is physaclly cyclic would require to check all the nodes until a cycle is found. This wont' terminate on infinite list in Haskell. However it will in Lisp (and probably all imperative languages), because cyclic list is the only way to do infinite list. — mb14, May 16 '15 at 12:54
@Bakuriu The function I proposed "returns `True` if the list is physically cyclic and `False` if the argument is of finite length. Otherwise it will fail to terminate." So the function `f` you proposed certainly would not return `2` for the value `ones`. — Jason Orendorff, May 21 '15 at 03:12

score 12 · Accepted Answer · edited May 23 '17 at 12:16

Would the existence of this function break any interesting properties of the language?

Yes it would. It would break referential transparency (see also the Wikipedia article). A Haskell expression can be always replaced by its value. In other words, it depends only on the passed arguments and nothing else. If we had

isCycle :: [a] -> Bool

as you propose, expressions using it would not satisfy this property any more. They could depend on the internal memory representation of values. In consequence, other laws would be violated. For example the identity law for Functor

fmap id === id

would not hold any more: You'd be able to distinguish between ones and fmap id ones, as the latter would be acyclic. And compiler optimizations such as applying the above law would not longer preserve program properties.

However another question would be having function

isCycleIO :: [a] -> IO Bool

as IO actions are allowed to examine and change anything.

A pure solution could be to have a data type that internally distinguishes the two:

import qualified Data.Foldable as F

data SmartList a = Cyclic [a] | Acyclic [a]

instance Functor SmartList where
    fmap f (Cyclic xs) = Cyclic (map f xs)
    fmap f (Acyclic xs) = Acyclic (map f xs)

instance F.Foldable SmartList where
    foldr f z (Acyclic xs) = F.foldr f z xs
    foldr f _ (Cyclic xs) = let r = F.foldr f r xs in r

Of course it wouldn't be able to recognize if a generic list is cyclic or not, but for many operations it'd be possible to preserve the knowledge of having Cyclic values.

I think you mean `fmap id ones`, not `fmap ones`. – amalloy May 17 '15 at 19:40 — amalloy, May 17 '15 at 19:40

score 0 · Answer 2 · answered May 16 '15 at 15:30

In the general case, no you can't identify a cyclic list. However if the list is being generated by an unfold operation then you can. Data.List contains this:

unfoldr :: (b -> Maybe (a, b)) -> b -> [a]

The first argument is a function that takes a "state" argument of type "b" and may return an element of the list and a new state. The second argument is the initial state. "Nothing" means the list ends.

If the state ever recurs then the list will repeat from the point of the last state. So if we instead use a different unfold function that returns a list of (a, b) pairs we can inspect the state corresponding to each element. If the same state is seen twice then the list is cyclic. Of course this assumes that the state is an instance of Eq or something.

Would the ability to detect cyclic lists in Haskell break any properties of the language?

2 Answers2

Linked