Ex3.hs

module Ex3 where

import Prelude hiding (last, (!!), map, id)

{-@ Induction examples from slide @-}

data Foo a = Nil | Cons  a (Foo a)
--    ^       ^    ^
--    |       |    |
--   type    data constructor
--  constructor

-- data FooF = NilF | ConsF Float FooF

-- foo = Cons 5 (Cons 3 Nil)
-- foo1 = Cons 5.3 Nil
-- foof = ConsF 5.3 NilF

{-@

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


Cons 1 (Cons 2 (Cons 3 Nil))

1 `Cons` 2 `Cons` 3 `Cons` Nil -- infix

1 : 2 : 3 : []

[1, 2, 3] = 1 : 2 : 3 : []
              ^          ^
              |          |
             Cons       Nil
foo :: [a] ->......
foo (x : xs) = .......
x = 1; xs = [2, 3]
foo [1, 2, 3]


@-}

{-@

Parametric Polymorphism -- forall a . a -> a
Ad-hoc Polymorphism -- Typeclasses - Num a => a -> a

@-}


id :: a -> a -- Permissive
id x = x     -- Restrictive
-- last [1, 2, 3] = 3

-- Partial
last :: [a] -> a
last [x] = x
last (_ : xs) = last xs

-- | Partial vs Total Function

-- | Can you define a Haskell datatype for which `last` is total?

-- data Maybe a = Nothing | Just a
-- (!!) :: [a] -> Int -> Maybe a
-- xs !! n = if (length xs < n)
--           then Nothing
--           else Just (xs !!! n)
--                where
(!!!) :: [a] -> Int -> Maybe a
[] !!! _  = Nothing
(x:xs) !!! 0  = Just x
(x : xs)  !!! n = xs !!! (n - 1)


-- | Write a total version of (!!)


{-@ Higher order function @-}

map :: (a -> b) -> [a] -> [b]
map f xs = [f i | i <- xs ]