Self-referential data type with single constructor cannot be `Show`n

Question

This is from The Little MLer. I have this

data Chain = Link Int (Int -> Chain)

and this

ints :: Int -> Chain
ints n = Link (n+1) ints

I'm rather confused as to what exactly is happening here. It seems like an endless recursion of itself where intson the left-hand side is just repeating the whole ints endlessly. The book is saying

[...] we may think of ints as a very long sequence of ints. We go from one element in this sequence to the next by applying the second component of ints n to the first.

I'm not sure how it does this. But then this produces an error

> ints 0
* No instance for (Show Chain) arising from a use of `print'
:     * In a stmt of an interactive GHCi command: print it

An attempt to tack on deriving Show won't fly

data Chain = Link Int (Int -> Chain) deriving Show
No instance for (Show (Int -> Chain))
        arising from the second field of `Link' (type `Int -> Chain')
        (maybe you haven't applied a function to enough arguments?)
      Possible fix:
        use a standalone 'deriving instance' declaration,
          so you can specify the instance context yourself
    * When deriving the instance for (Show Chain)

Not sure what is going on or how to proceed. Any similar examples would be appreciated.

---

Update

Here's the SML code

datatype chain = Link of (int * (int -> chain))
fun ints (n) = Link (n+1, ints)
> ints(0)
val it = Link (1,fn) : chain

Not totally sure, but that fn is the SML way of doing anonymous, i.e. fn is their \. This might just be a coincidence.

So what's SML got that Haskell can't handle? Is this something to do with Haskell being pure and SML is not?

Answer 1

What is going on is this:

current :: Chain -> Int
current (Link i _) = i

next :: Chain -> Chain
next (Link i g) = g i

just as the quote is saying. Your ints is a function, so nothing infinite is going on here, just a delayed possibility of function application to get the next Link in a chain so the next Int can be found as its current element.

As for the printing,

printLink :: Link -> String
printLink (Link i _) = "{Link of " ++ show i ++ " }"

is one possible definition. There's nothing informative we can say about the function so we will just have to ignore it.

Example interaction:

ch1 = ints 0
i1 = current ch1  -- 1
ch2 = next ch1  
i2 = current ch2  -- 2

etc.

Next we can define takeN :: Int -> Chain -> [Int] so that takeN 5 ch1 returns the list of five Ints from the chain ch1, i.e. [1,2,3,4,5].

SML is strict, it can't have infinite lists like Haskell can. So instead, SML represents the "next" computation by a function, which you have to invoke explicitly.

Since Haskell is lazy, we cold also just define chainToList :: Chain -> [Int] to convert a chain to an infinite list of entries in it, and then use the standard function take on that.

In your new SML example, "fn" is just an indicator that there's a function there, some function. In your case it's the function ints but the run-time system apparently doesn't know that. This probably means that any function will get printed as "fn" in SML as your example shows.

But you don't need to print it to use it.