HiveBrain v1.2.0
Get Started
← Back to all entries
patternModerate

Which fixpoint is Haskell list type?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
typefixpointhaskellwhichlist

Problem

Let's say that lists are defined as

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.