Custom List Data Type WIP

list.hs

data List a = Empty | Cons a (List a) deriving (Eq)


instance Show a => Show (List a) where
  show list = "(" ++ showListContents list ++ ")"


showListContents :: Show a => List a -> String
showListContents Empty = ""
showListContents (Cons x Empty) = show x
showListContents (Cons x xs) = show x ++ " " ++ showListContents xs


instance Functor List where
  fmap f Empty = Empty
  fmap f (Cons x xs) = f x `cons` fmap f xs


singleton :: a -> List a
singleton x = Cons x Empty


infixr 5 `cons'`
cons' :: a -> List a -> List a
cons' = prepend . singleton


infixr 5 `cons`
cons :: a -> List a -> List a
cons = Cons


prepend :: List a -> List a -> List a
prepend Empty ys = ys
prepend (Cons x xs) ys = Cons x (prepend xs ys)


append :: List a -> List a -> List a
append xs Empty = xs
append xs (Cons y ys) = Cons y (append xs ys)

--
-- -- this should be provided by making it an instance of functor
-- map' :: (a -> b) -> List a -> List b
-- map' _ Empty = Empty
-- map' f (Cons x xs) = Cons (f x) (map' f xs)


isEmpty :: List a -> Bool
isEmpty Empty = True
isEmpty _ = False

-- 
-- isSingleton :: List a -> Bool
-- isSingleton (Cons _ Empty) = True
-- isSingleton _ = False


length' :: List a -> Int
length' Empty = 0
length' (Cons _ xs) = 1 + length' xs


list :: List Int
list = 5 `cons` 7 `cons` 2 `cons` Empty


list2 :: List Int
list2 = 9 `cons` 1 `cons` Empty


list3 :: List Int
list3 = append list2 list

notes

data List' a = Empty | Cons a (List' a) deriving (Show)

list = Cons 5 (Cons 7 (Cons 2 Empty))

ghci> :l List.hs
ghci> list
Cons 5 (Cons 7 (Cons 2 Empty))


instance Show a => Show (List' a) where
  show list = "[" ++ showListContents list ++ "]"


showListContents :: Show a => List' a -> String
showListContents Empty = ""
showListContents (Cons x Empty) = show x
showListContents (Cons x xs) = show x ++ "," ++ showListContents xs

note: Cons x Empty used to remove trailing commas [5,7,2,] <-

ghci> list
[5,7,2]


** Or as an homage to lisp (http://en.wikipedia.org/wiki/Cons
), and to clearly differentiate our list from hassle’s default list

instance Show a => Show (List a) where
  show list = "(" ++ showListContents list ++ ")"


showListContents :: Show a => List a -> String
showListContents Empty = ""
showListContents (Cons x Empty) = show x
showListContents (Cons x xs) = show x ++ " " ++ showListContents xs

*Main Data.Functor> list

(5 7 2) 


Now how to add easier list additions? Would have to manually type
Cons 8 (Cons …)

cons :: a -> List' a -> List' a
cons = Cons

(effectively `cons` is our alias for the Cons value constructor)

We could use infix style 5 `Cons` 7 `Cons` … but that if bad form making end users use our value constructor, let’s provide a function for adding values:

cons :: a -> List' a -> List' a
cons = Cons

Simple, we could have gotten creative and used a symbol, >, etc. but this is cool

list :: List' Int
list = 5 `cons` (7 `cons` (2 `cons` Empty))

Looks a little better, but not great, let’s try to write it more like the native cons (:) operator

list :: List' Int
list = 5 `cons` 7 `cons` 2 `cons` Empty

ghci> :l List.hs
No instance for (Num a0) arising from the literal ‘5’

    The type variable ‘a0’ is ambiguous

    Relevant bindings include

      list :: List' (List' (List' a0)) (bound at junk.hs:23:1)

  …



Well, that didn’t work. We used `cons` correctly as an infix operator, but haskell doesn’t know that we want right associativity. Be default, it will try to read our line left to right, which would result in (5 `cons` 7) …. That’s not what we want.

 If no fixity declaration is given for a particular operator, it defaults to infixl 9

https://www.haskell.org/tutorial/functions.html

Read right to left, like other syntax.

Declare right associative infix

infixr 5 `cons`




Let’s add an append function - this should add a list to the end of a list

append :: List' a -> List' a -> List' a
append xs (Cons y Empty) = Cons y xs
append xs (Cons y ys) = Cons y (append xs ys)

list2 :: List' Int
list2 = 9 `cons` (1 `cons` Empty)

list3 :: List' Int
list3 = append list2 list

ghci> list3
[5,7,2,9,1]


prepend

singleton function

refactor cons to
cons = prepend . singleton