My redefinition of Haskell 'length' function won't work

user_13020870 0
Viewed 167

Can someone please explain how I can fix my program. Very new to Haskell, been trying to create a length function that calculates the length of a list of any type.

I am aiming to do this using data as I want to create a brand new type to do so (this is the area of Haskell that I'm currently learning, which is why it might not be the most efficient implementation of this function)

data List a = Nil | Cons a (List a)


len :: List a -> Int
len Nil         = 0
len (Cons _ xs) = 1 + len xs

If I run it on len [1,2,3] I get the error:

 • Couldn't match expected type ‘List a0’
                  with actual type ‘[Integer]’
    • In the first argument of ‘len’, namely ‘[1, 2, 3]’
      In the expression: len [1, 2, 3]
      In an equation for ‘it’: it = len [1, 2, 3]
type-mismatch algebraic-data-types recursion list haskell
1 Answers

The function definition is correct, but [1,2,3] is not a List a object, it is a [a] (or more canonical [] a). A list like [1,2,3] as List Int is:

len (Cons 1 (Cons 2 (Cons 3 Nil)))

Alternatively, you can make List a an instance of the IsList type class, and then use the -XOverloadedLists extension:

{-# LANGUAGE TypeFamilies #-}

import GHC.Exts(IsList(Item, fromList, toList))

instance IsList (List a) where
    type Item (List a) = a
    fromList = foldr Cons Nil
    toList Nil = []
    toList (Cons x xs) = x : toList xs

Then we can use the OverloadedLists extension:

$ ghci -XOverloadedLists -XTypeFamilies
GHCi, version 8.0.2: http://www.haskell.org/ghc/  :? for help
Loaded GHCi configuration from /home/kommusoft/.ghci
Prelude> data List a = Nil | Cons a (List a)
Prelude> import GHC.Exts(IsList(Item, fromList, toList))
Prelude GHC.Exts> :{
Prelude GHC.Exts| instance IsList (List a) where
Prelude GHC.Exts|     type Item (List a) = a
Prelude GHC.Exts|     fromList = foldr Cons Nil
Prelude GHC.Exts|     toList Nil = []
Prelude GHC.Exts|     toList (Cons x xs) = x : toList xs
Prelude GHC.Exts| :}
Prelude GHC.Exts> :{
Prelude GHC.Exts| len :: List a -> Int
Prelude GHC.Exts| len Nil         = 0
Prelude GHC.Exts| len (Cons _ xs) = 1 + len xs
Prelude GHC.Exts| :}
Prelude GHC.Exts> len [1,2,3]
3
user_675790
Related