Perl, Haskell, stuff
This is an interesting chapter, working on the higher order functions rather than actually drawing shapes.
It covers:
I asked on irc and had a few good answers, or rather questions, such as “What do you do with the empty list?” and “What happens when they're different types?” (Note in fact that there are potentially two types, a and b.
*Five> :t foldl
foldl :: (a -> b -> a) -> a -> [b] -> a
But in fact there is a version that takes the first element, called foldl1.
One of the nice things I'm beginning to discover about fold is that you can use the init argument as a sort of accumulator, for example [], I think I have examples of this a bit later.
Obviously “non-recursive” really means without explicit recursion (although I suppose once you have abstracted it that way, the implementation could choose to do the mapping non-recursively as an optimization).
The original was like this:
> -- this is the original function from section 2.2
> area_orig (Polygon (v1 : vs)) = polyArea vs
> where polyArea :: [Vertex] -> Float
> polyArea (v2 : v3 : vs') = triArea v1 v2 v3
> + polyArea( v3 : vs')
> polyArea _ = 0
I mutated it into a version using a fold (in the form of sum), but then I got stuck and had to invent my own higher order function, map2, which iterates 2 list items at a time.
> import Shape
>
> map2 :: (a -> a -> a1) -> [a] -> [a1]
> map2 f (a1 : a2 : as) = (f a1 a2) : map2 f (a2 : as)
> map2 _ _ = []
>
> area_new (Polygon (v1 : vs))
> = let doTri v2 v3 = triArea v1 v2 v3
> in sum $ map2 doTri vs
Thinking that maybe I should try using just functions that have been mentioned up until now, I tried the same using zip (of vs and tail vs), which is a cute trick I read later in the book I think... I had the lovely experience of writing the algorithm in Haskell as fast as I could think, and it working first time!
> area_new2 (Polygon (v1 : vs))
> = let doTri (v2, v3) = triArea v1 v2 v3
> in sum $ map doTri $ zip vs (tail vs)
I don't really understand this. I know that “map map” returns a new curried function, but we haven't covered that yet, and I'm a bit baffled.
> :t map
map :: (a -> b) -> [a] -> [b]
In “map map”, the first map takes a function which is map, which goes from (a->b) to [a]->[b]. So
-- On writing this up properly, I don't even understand what
-- the following snippets were trying to get at...
map map :: ((a->b) -> ([a] -> [b])) -> ??
map (+1) $ map (*2) [1,2,3]
but no, we want
map map
which means map a function that maps stuff over the argument. This is making me crabby, so I tried it out:
*Five> :t map map
map map :: [a -> b] -> [[a] -> [b]]
Ok, so this maps a list of functions (a->b) to a list of functions ([a]->[b]). Right now I feel like crying, I don't know what this is for, I think this question is an unpleasant and confusing one in the middle of some decent exercises. That, or I'm missing something obvious. Either way, I'm giving up and moving on.
Update: I discussed on #haskell, the suggestion was made that map upgrades a function (a->b) to being ([a]->[b]).
So,
> map :: (a->b) -> ([a]->[b])
> map map :: [(a->b)] -> [([a]->[b])]
OK. Right now, that isn't looking as impossible to understand as I'd previously thought (though I'd still like to see an example of map map used in anger,) so let's look at the next one, “foldl foldl”
> foldl :: (a -> b -> a) -> a -> [b] -> a
> foldl foldl :: ?
OK, The following is trying to substitute a with (a->b->a):
> foldl foldl :: ((a->b->a) -> b -> (a->b->a)) -> (a->b->a) -> [b] -> (a->b->a)
but that isn't the way we did it for map. First of all we formatted the type in a way that it was recognizably the same as the type of the expected function. And here's a thing
> foldl :: (a -> b -> a) -> a -> [b] -> a
doesn't match (a->b->a).
*Five> :t foldl foldl
<interactive>:1:6:
Couldn't match expected type `b -> [b]' against inferred type `[b]'
In the first argument of `foldl', namely `foldl'
I'm not quite sure what this question was trying to get at in this case, apart from beware of trick questions.
Let's try one more time with the last item, “map foldl”.
> map :: (a->b) -> ([a]->[b])
> foldl :: (a -> b -> a) -> (a -> [b] -> a)
> map foldl :: ?
Is it...
> map foldl :: [a->b->a] -> [a->[b]->a] -- ?
Yes it is, callooh callay. Still, I would cut this exercise out, or move it to a point in the text where it's clearer what to do with it.
My first thought on this is that you can sum 1 for each item in the list, so
> length2 :: [a] -> Int
> length2 xs = sum $ map (\x ->1) xs
But something which I finally understood about the init argument of fold, that it's an accumulator means that you can do
> length3 xs = foldl (\acc _ -> acc+1) 0 xs
See, we're folding over the elements but not using them at all (hence the _), the accumulator is doing all the work. I think that's quite cute.
Using the higher order functions that we've now defined, fill in the two missing functions, f1 and f2, in the evaluation below so that it is valid:
> f1 (f2 (*) [1,2,3,4]) 5 => [5,10,15,20]
f2 is likely to be a map:
(map (*) [1,2,3,4])
=> [(1*), (2*), (3*), (4*)]
so f1 is something like a reverse map
> unmap (v:vs) x = (v x) : unmap vs x
> unmap [] _ = []
*Five> unmap (map (*) [1,2,3,4]) 5
[5,10,15,20]
Except that unmap (which is almost certainly defined in the Standard Prelude with a better name/implementation) isn't one of the functions we already defined, so this answer might not be to specification.
As these are easy questions, I just defined these at the ghci prompt:
*Five> let doubleEach xs = map (*2) xs
*Five> doubleEach [1,2,3]
[2,4,6]
*Five> let pairAndOne xs = map (\x -> (x,x+1)) xs
*Five> pairAndOne [1,2,3]
[(1,2),(2,3),(3,4)]
*Five> let addEachPair xs = map (\(a,b) -> a + b) xs
*Five> addEachPair [(1,2),(3,4),(5,6)]
[3,7,11]
I love how you can pattern match on tuples, very cool.
*Five> let maxList xs = foldl (\a b-> if a > b then a else b) 0 xs
*Five> maxList [6,7,5,8,4,9,2]
Of course this won't work with negative numbers:
*Five> maxList [-6,-7,-5,-8,-4,-9,-2]
0
We could use the first element of the list, but we need to manage the case in which there is none (e.g., the empty list)
> maxList (v:vs) = foldl (\a b -> if a > b then a else b) v vs
> maxList [] = 0
Of course there's a nice function “max” that does the same as that lambda
> maxList (v:vs) = foldl max v vs
> maxList [] = 0
analogously
> minList (v:vs) = foldl min v vs
> minList [] = 0
but I guess at this point we'd want to abstract these similar functions.
> foldlf f base (v:vs) = foldl f v vs
> foldlf _ base _ = base
>
> maxList xs = foldlf max 0 xs
> minList xs = foldlf min 0 xs
Which is more or less the same as the standard foldl1 higher order function, except that that one seems to just throw an exception in the case of an empty list (which actually, when you think about it, does make some sense - is the “maximum” of an empty list really 0?)
*Five> let addPairsPointwise xs
= foldl (\(x1,y1) (x2,y2) -> (x1+x2, y1+y2)) (0,0) xs
*Five> addPairsPointwise [(1,2),(3,4),(5,6)]
(9,12)
> incChar, decChar :: Char -> Char
> incChar c = toEnum $ (fromEnum c) + 1
> decChar c = toEnum $ (fromEnum c) - 1
>
> encrypt, decrypt :: String -> String
> encrypt s = map incChar s
> decrypt s = map decChar s
Let's try this out:
*Five> encrypt "Hello Francine!"
"Ifmmp!Gsbodjof\""
*Five> decrypt "Ifmmp!Gsbodjof\""
"Hello Francine!"
While I was playing around with this, I came across an interesting oddity:
*Five> fromEnum 'x'
120
*Five> toEnum 120
120
*Five> toEnum $ fromEnum 'x'
120
The explanation seems to be that the last “120“ isn't a common or garden 120:
*Five> :t 120
120 :: (Num t) => t
*Five> :t toEnum 120
toEnum 120 :: (Enum a) => a
This is a “generic Enum” of value 120. In fact, if we constrain the type, we get ‘x’ as expected:
*Five> toEnum 120 :: Char
'x'
Which is what's happening with the functions incChar and decChar above: the typing sorts them out.
*Five> decChar 'x'
'w'
If we commented the type:
-- incChar, decChar :: Char -> Char
Then we get the unspecified Enum again:
*Five> decChar 'x'
119
But
*Five> encrypt "Hello Francine!"
"Ifmmp!Gsbodjof\""
still works! Because the string is still constrained. If we commented that line too...
-- encrypt, decrypt :: String -> String
Then we get
*Five> encrypt "Hello Francine!"
[73,102,109,109,112,33,71,115,98,111,100,106,111,102,34]
I don't know why this idea tickles me so much, but I had fun playing around with various other Enums like Bool
*Five> toEnum 0 :: Bool
False
*Five> toEnum 1 :: Bool
True
*Five> toEnum 2 :: Bool
*** Exception: Prelude.Enum.Bool.toEnum: bad argument
makeChange 99 [5,1] => [19,4]
We can assume that the coin denominations are in descending order, and that the unit coin (of value 1) will always be present
This is just that bit tricky that I can't jump straight to the higher order definition. So, the first, recursive version:
> makeChange :: Int -> [Int] -> [Int]
> makeChange amt denominations
> = _makeChange amt denominations []
> where
> _makeChange :: Int -> [Int] -> [Int] -> [Int]
> _makeChange amt (denom:ds) ans
> = let num = amt `quot` denom
> left = amt `mod` denom
> in _makeChange left ds (ans ++ [num])
> _makeChange 0 [] ans = ans
> _makeChange _ _ _
> = error "This shouldn't happen due to assumptions"
I like the idea of using a fold with an accumulator. However, as we need to thread not just the current amount left, but also the answer, I ended up using a tuple and the following, which I think might be a little clumsy:
> makeChange :: Int -> [Int] -> [Int]
> makeChange amt denominations
> = snd $ foldl aux (amt, []) denominations
> where
> aux :: (Int, [Int]) -> Int -> (Int, [Int])
> aux (amt, ans) d
> = let num = amt `quot` d
> left = amt `mod` d
> in (left, (ans ++ [num]))
I wonder what the best way to do this would be. Also note that the function doesn't work for cases where taking the most of the current highest possible denomination is suboptimal. For example
12 [10,6,1]
=> [1,0,2] -- what we get
=> [0,2,0] -- the ideal
however this kind of coin system is generally unusual, and I think the answer would involve backtracking and is probably out of scope at this point. (Maybe one to come back to though!)
Osfameron's blog on Haskell, Perl programming, stuff.
Leave a reply