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?

Answer 1

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.