patternModerate
Which fixpoint is Haskell list type?
Viewed 0 times
typefixpointhaskellwhichlist
Problem
Let's say that lists are defined as
Then, in Haskell is
List a = Nil | Cons a (List a)Then, in Haskell is
List x the greatest or least fixpoint? I'm asking because the lfp should exclude infinite lists (but you can build them in Haskell), whereas the gfp should exclude finite ones.Solution
It's the greatest fixed point, or the final coalgebra, depending on how you set things up. In Haskell it is impossible to define the datatype of finite lists because Haskell does not have inductive types, only the coinductive ones. Many people are in denial about this particular issue.
Context
StackExchange Computer Science Q#30481, answer score: 10
Revisions (0)
No revisions yet.