Haskell Land

After playing around a bit with Haskell (I’ve finished the first few chapters in Learn You a Haskell For Great Good which is awesome, I highly recommend it, even if just for the fun drawings), I’ve finally reached the point where I can write the code for the lists I previously played with in To Curse and Recurse.

So, without further ado, here’s the code (and some other functions as well – these were all part of a Theory of Algorithms homework):

append :: [a] -> [a] -> [a]
append (x:l1) l2 = x : (append l1 l2)
append [] l2 = l2

-- this would take O(n^2) time : (
reverse' :: [a] -> [a]
reverse' (x:l) = append l' [x] -- <- the culprit is here, *append*
        where l' = reverse' l
reverse' [] = []

-- this only takes O(n)
reverse'' :: [a] -> [a]
reverse'' (x:l) = reverse_a l [x]

reverse_a :: [a] -> [a] -> [a]
reverse_a (x:l1) l2 = reverse_a l1 (x:l2)
reverse_a [] l2 = l2

--
member :: (Eq a) => a -> [a] -> Bool
member a (x:l) = if x == a
                 then True
                 else (member a l)
member a [] = False

--
size :: [a] -> Integer
size (x:l) = 1 + (size l)
size [] = 0

-- maxelem [] is not defined! it does not make sense
maxelem :: (Ord a) => [a] -> a
maxelem [x] = x
maxelem (x:l) = max x (maxelem l)

-- different 'tail' version
maxelem' :: (Ord a) => [a] -> a
maxelem' (x:l) = maxelem_a l x

maxelem_a :: (Ord a) => [a] -> a -> a
maxelem_a (x:l) m = maxelem_a l (max x m)
maxelem_a [] m = m

--
minelem :: (Ord a) => [a] -> a
minelem [x] = x
minelem (x:l) = min x (minelem l)

--
set :: (Eq a) => [a] -> [a]
set (x:l)
    | member x s = s
    | otherwise = x:s
    where s = set l
set [] = []

set' :: (Eq a) => [a] -> [a]
set' (x:l) =
     let s = set l
     in if (member x s)
        then s
        else x:s
set' [] = []

--
nbrelems :: (Eq a) => [a] -> Integer
nbrelems l = size (set l)

-- from a different set of exercises
-- but really, these comments are worthless : D
remove :: (Eq a) => a -> [a] -> [a]
remove a (x:l)
       | a == x = l'
       | otherwise = x:l'
       where l' = remove a l
remove a [] = []

--
double :: (Eq a) => a -> [a] -> [a]
double a (x:l) =
       let l' = double a l
       in
        case a == x of
             True -> a:x:l'
             False -> x:l'
double a [] = []

Yes, so congrats to me for reimplementing functions that were already in the Prelude! I feel so very useful 😉 Anyway, this just might be the beginning of a beautiful friendship…

Also, who else is annoyed that Haskell syntax is not supported by WordPress? But, well I’m just thrilled they have syntax highlighting for much more useful and interesting languages like… ColdFusion or ActionScript.

Advertisements