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

user_2394634 0
Viewed 152

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?

self-reference sml haskell types
3 Answers

In general there is no good way to Show a function, so Haskell will not make an instance of Show for you when a function is involved..

You could write one yourself:

instance Show Chain where
  show (Link n fn) = ...

But now you have to figure out how to show fn:: Int->Chain. In Haskell at least functions are atomic and opaque. You can't break them apart or inspect their contents, only apply them.

user_1631770

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.

user_8498910

This is a case of having not read ahead far enough in the text, as well as getting a false positive from one language (SML) but not the other. As it turns out, getting a Chain returning function like ints to do direct output is a misapplication. These Chain "generators" are only there as an intermediary for another function to "look up" what is where in such a Chain object, in TLMLer's examples, the next integer in the second part of the data constructor.

data Chain = Link Int (Int -> Chain)

So consider another Chain generator fiveOrsevenInts

mod5or7 n = if (evenDiv n 5) then True else (evenDiv n 7)
                where evenDiv a b = ((a `mod` b) == 0)

fiveOrsevenInts n = if (mod5or7 (n+1))
             then (Link (n+1) fiveOrsevenInts)
             else fiveOrsevenInts (n+1)

fiveOrsevenInts creates a Chain based on numbers divisible by 5 or 7. As I learned, the whole idea is getting a "read ahead" of the "chain." So if

fiveOrsevenInts (1) => Link 5 fiveOrsevenInts

the trick is to get fiveOrsevenInts (the Int -> Chain function) to act on the 5 to get the next Int in the chain. And as I mistakenly thought, we don't need to "see" the above direct resolution of fiveOrsevenInts (1) at all.

A general function to take desired position in the chain sequence and a chain-producing function like fiveOrsevenInts and give back the member for that position would be

chainItem n (Link i f) = if (n == 1)
                         then i
                         else chainItem (n-1) (f i)

Now if I want to see the first in a sequence of integers multiples of 5 or 7 it's just

chainItem 1 (fiveOrsevenInts 0)
5
chainItem 2  (fiveOrsevenInts 0)
7
chainItem 3  (fiveOrsevenInts 0)
10
...
chainItem 37  (fiveOrsevenInts 0)
119

where fiveOrsevenInts 0 "seeds" the Chain. Later in the chapter this strategy is applied to finding a sequence of primes by building a prime Chain generator. All in all, I'm finding The Little MLer a fun way to learn its sibling Haskell. When I'm through I'll try to share my overall translation.

user_23946340
Related