I stumbled upon some question that puzzled me, maybe it’s just a feature (or simply because I am doing first “Haskell-steps” without studying the manual too deeply, which I guess I should…
Anyway, the observation want to ask about is as follows: I did some inductive data type definition, though it’s “non-regular”, i.e., requiring polymorphic recursion. I am aware that this is problematic, so I wanted to see to what extent Haskell can handle it. The actual code is at the end of the post.
Ultimately, what I don’t understand is the difference in behavior comparing – doing a :load file.hs in the ghci as opposed to – typing in the definitions manually inside the ghci.
Actually, I am not 100% sure if it has to do with the particular kind of recursion (though for simpler things I did, no such discrepancy showed up.
For concreteness sake, the code looks like the one below: The non-regular data structure is SList (strange list). The datatype in isolation works both with loading the file or typing it manually. I am not surprized by that part. More interesting and the cause of the problem is the function slength. It’s kind of an instance of polymorphic recursion and thus potentially problematic. On the other hand, the non-regularity of the type parameter a vs. Node a, vs. Node (Node a)) etc is not really relevant in the inductive definition.
Indeed, the whole code loads fine in GHCi version 8.6.5, though clipping it in fails, reporting as failure that “Occurs check: cannot construct the infinite type”. Also this seems understandable, caused by the polymorphic recursive definition of slength. What I don’t understand is, why both ways of doing things in ghci behave differently (BTW also compiling with ghc works)
data Node a = Pair a a
data SList a = Nil | Cons a (SList (Node a))
slength :: SList a -> Int
slength Nil = 0
slength (Cons n r) = 1 + (slength r)