Perl, Haskell, stuff
Random numbers seem to be a bit of a pain in Haskell. Because they are not a “pure” function (they involve hooking up with a system or user-supplied random number generator) there is a little scaffolding involved. Also when the number comes back, it's wrapped in an IO Ref, making the whole of your function impure — causing me at least a fair amount of grief.
I got stuck trying to do something more complicated and then went back to a simpler task: implementing a function pick
> pick :: [a] -> a
or rather
> pick :: [a] -> IO a
which will return an element from [a], chosen at random
The first, obvious implementation is
> pick a = do r <- getStdRandom (randomR (1, length a))
> return $ a !! (r-1)
The getStdRandom is the boilerplate I was mentioning (there may be better ways of doing this — I just cargo culted from the Haskell Report) while randomR gives a random integer in the range (min,max) provided.
This is (for once) rather longer than the equivalent Perl
sub pick { $_[rand( @_ )] }
It's also inefficient, as we have to scan all the elements of a to get the length and then another r elements to do the indexing.
There's a lovely algorithm to choose a random element of a sequence that only involves scanning it once. You start with your first element and select it. You move to the second element, and have a probability of (1/2) of selecting it. You move to the third, with a probability of (1/3)
Here's my code for it:
> pick :: [a] -> IO a
> pick [] = undefined
> pick [x] = do return x
> pick (x:xs) = pick' x xs 2
>
> pick' :: (Num p, Random p) => t -> [t] -> p -> IO t
> pick' curr [] _ = do return curr
> pick' curr (next:rest) prob
> = do r <- getStdRandom (randomR (1,prob))
> let curr' = if r == 1 then next else curr
> pick' curr' rest (prob+1)
Why in the auxhiliary function pick’ does p get typed as Random? As far as I can see, it's just a number, it increases monotonically and only participates in the function randomR as an upper bound.
Now this works in ghci:
*Main> pick [1,2,3,4,5]
3
Now if we want a list of random numbers:
*Main> map (\_ -> pick [1..5]) [1..5]
<interactive>:1:0:
No instance for (Show (IO t))
arising from use of `print' at <interactive>:1:0-32
Possible fix: add an instance declaration for (Show (IO t))
In the expression: print it
In a 'do' expression: print it
This is annoying. OK, maybe an IO value can't be showable because show returns a String, not an IO String, so using Show would allow you to subvert the IO sandbox. Or something. But if ghci can fake it in the case of a single IO value, why can't it do something sensible for a list of IO values?
Some interesting comments also on the algorithm to choose random numbers. Fair comment that my description of it is a little confusing - by "select", I mean "change the currently selected number for the new number". But the code is quite clear - evir and Sorear pointed out that Nethack (at least 3.4.3) has a citation of the algorithm and a proof in the comments! (in eat.c Elliott Kleinrock, October 5, 1990)
I was playing with the Maybe type and realised that there are useful functions provided to play with these types.
Then I realised that in my definition of ternary operator in haskell the definition of (!)
> Nothing ! a = a
> Just b ! _ = b
was very similar to the predefined function fromMaybe (only with its arguments reversed)
In fact, we can define the ternary operator using functions defined in Data.Maybe!
> (?) = boolToMaybe
> (!) = flip fromMaybe
Ok ok, that's not quite true. boolToMaybe doesn't exist in Data.Maybe, but the similar listToMaybe does.
We'd have to define
> boolToMaybe True a = Just a
> boolToMaybe False _ = Nothing
Or, a cute but less clear version (that makes clear the heritage with listToMaybe):
> boolToMaybe b v = listToMaybe $ filter (const b) [v]
For some time I've been wanting to implement the Enfilade, a really cool data structure discovered by the Xanadu people among others. It's like a balanced tree, except that it's indexed relatively rather than absolutely - making it ideal for things like text editor buffers, as you can insert and delete with impunity, knowing that the changes to the address of pieces to your right will percolate up the tree.
As there isn't already an implementation on Perl's CPAN I've occasionally planned to do it for fun.
Problems: 1) I'm lazy, and 2) I'm weak in Computer Science, so I don't even know how to do the balanced binary tree that I need as a basis. I looked on CPAN some time back, which has some implementations of trees, but I couldn't figure out how to get them relatively indexed, and besides which, it's always instructive to implement something for yourself.
I bought Okasaki's “Purely Functional Data Structures” some time back, in a fit of enthusiasm, read the first chapter (a very readable introduction) and been utterly terrified by the rest of it. But recently I picked it up off the shelf, read and mostly understood the chapter on Red Black trees, and had a go implementing it with Perl.
Why a purely functional version? As Okasaki says, the algorithm is simpler than the destructive one (and potentially very fast). Also I think that having a persistent, functional tree will make it trivial to implement things like “undo”.
A quick look at the algorithm suggested that I might want lazy building of the tree structure, and that reminded me of the overview in Moose's cookbook about a lazy binary tree.
Oddly, the Moose example has “parent” fields, which rather defeat the point of sharing, but then again Moose is an OO base class, not an FP language so fair enough. But I've been meaning to learn Moose for a while so this seemed like a perfect opportunity.
Five hours later (I'm a bit slow, but I suppose that's not bad as I'm grokking a new library and an algorithm at the same time) I have a working implementation.
Some notes:
Node
|-> Node::E - empty node
`-> Node::T - full node
This isn't a criticism of Moose of course - it's designed for OO systems, and there, the amount of work that Moose does makes your code powerful and readable, and some Very Clever People in the Perl world are developing it, using it, and making it fast.
But an FP algorithm uses many short lived structures, which may make this overhead untenable. Certainly my test script was noticeably slow, and profiling may have pointed to Moose as the culprit.
Actually the other profiling modules (like DProfLB - where LB stands for “Less Bad” seem to do the same thing) Pah.
It makes certain aspects of implementing algorithms in an FP style very neat to prototype, but seems to be impractical due to the overhead on short-lived objects. I wouldn't have any reservations to using it for an OO class though!
You can see the Moosey and non-Moosey code in my svn repo.
I've been back to Edinburgh for a family reunion and got to spend a morning with my dad who's a maths teacher by trade — I always thought he might be interested in haskell but never got the time to really look at some stuff in a bit of detail. I'd been pointed at Project Euler and thought it would be an interesting thing to look at together.
We worked through 5. What is the smallest number divisible by each of the numbers 1 to 20?
We started off with factorial of 20, and then the product of the primes in the range. Which meant we needed a sieve. I'd written a sieve in Perl (using HOP::Stream
sub pf {
my $s = shift;
my $head = drop $s;
my $s2 = filter { $_[0] % $head } $s;
return node($head, promise { pf($s2) } );
}
I still don't find this technique (wrapping filtering coderefs around each other in a lazy stream) natural, and it took me a while to translate this haskellish technique back into haskell...
> makeSieve n = filter (\i -> i `mod` n /= )
> primes [] = []
> primes (x:xs) = x : (primes $ (makeSieve x) xs)
Which is all very nice, but of course this is not the right number:
> *Main> primes [2..20]
> [2,3,5,7,11,13,17,19]
> *Main> product $ primes [2..20]
> 9699690
The right answer is the product of all the numbers 1..20 except for the ones that are already included in another number. So for example 20*19*18*... but not including 10,5,4, as they're already factors of 20.
We had the idea that we needed to get the factors of each number, so that we could then throw out those whose factors have already been used.
So here's a nice prime factorization technique:
> factorize n = factorize' n (primes [2..]) []
>
> factorize' n (p:px) results
> | n == 1
> = results
> | n `mod` p ==
> = factorize' (n `quot` p) (p:px) (p:results)
> | otherwise
> = factorize' n px results
Used like this
> *Main> factorize 18
> [3,3,2]
But now we want to know the powers of each factor: e.g. in this case, 3^2 and 2^1.
> powf n = map (\l -> (head l, length l) ) $ groupBy (==) n
It made sense for the result to come back as tuples of (value, power):
> *Main> powf $ factorize 18
> [(3,2),(2,1)]
And we can get the whole lot like so:
> *Main> map (powf.factorize) [1..20]
> [[],[(2,1)],[(3,1)],[(2,2)],[(5,1)], ....
But now we just want the maximum power for each one. I tried to get my brain in gear to work out how to do this recursively, then gave up and decided to just sort them...
We sort by value and the descending power. It made sense to use the library function sortBy, which takes a sorting function:
> cmp (a,a') (b,b') | a == b = compare (b') (a')
> | a < b = LT
> | otherwise = GT
(compare is the inbuilt function that compares two Ord values)
> *Main> sortBy cmp $ concatMap (powf.factorize) [1..20]
Now we want the top power for each value. The way that came to mind was to group by the value:
> groupBy (\(x,_) (y,_) -> x == y) $
> sortBy cmp $ concatMap (powf.factorize) [1..20]
Now that we've grouped we just want the maximum ord for each:
> map (\l -> head l) $
> groupBy (\(x,_) (y,_) -> x == y) $
> sortBy cmp $ concatMap (powf.factorize) [1..20]
Giving us (value,power) pairs like so:
> [(2,4),(3,2),(5,1),(7,1),(11,1),(13,1),(17,1),(19,1)]
And then of course we want to exponentiate these value:
> let factors = map (\(n,p) -> n ^ p ) $
> map (\l -> head l) $
> groupBy (\(x,_) (y,_) -> x == y) $
> sortBy cmp $ concatMap (powf.factorize) [1..20]
Now it's just a matter of
> *Main> product factors
And Bob's your uncle. What could be simpler? ;-)
I clicked through to the Project Euler discussion forums to see a nice Ruby version:
num = (1..20).inject(1) { |result, n| result.lcm n }
OK, Ruby still seems weird to me, but that's because I haven't learnt it. The point is that this seems rather more compact. As soon as I pointed this to my Dad, he said, “Of course it's a least common multiple problem”. Which of course is more or less the approach that we'd taken, but rather more verbosely than the Ruby version.
So I googled “haskell lcm” to check if there was a function with a similar name somewhere. There was indeed a function lcm... in the Prelude itself.
“Oh,” I said, “maybe this will work...” and typed the following into ghci:
> foldl1 lcm [1..20]
This of course is equivalent to the above... but 20 times shorter. This is both humbling and rather interesting. I think it was worth going through the entire process to get to this point, as I learnt a lot. Also, now having an (inefficient) prime sieve and a prime factoriser, I can easily solve a number of other questions:
3: Find the largest prime factor of 317584931803.
> *Main> factorize 317584931803
7: Find the 10001st prime number
> *Main> show $ last (take 10001 $ primes [2..])
(This one takes quite a long time - about 12 seconds - to complete. Apparently there are much better sieves, but we're still comfortably within the project's “minute rule” so I'm not going to prematurely optimize yet!
Update: bluestorm points out that what I believed to be a Sieve of Eratosthenes actually isn't, citing The Genuine Sieve of Eratosthenes, a very readable paper on the topic.
I banged my head against this exercise on fix for far too long.
I've confused myself enough times trying to understand “The Why of Y” paper that I have this silly idea that fixed point combinators (if that's the right terminology) are somehow hard
I don't think that setting the question with the hint “(This is tricky!)“ and then expecting your student to work out recursion using fix by themselves is really good pedagogic practise.
quicksilver on #haskell showed his charitable nature in two ways:
Firstly, by suggesting that perhaps Hudak is expecting the teacher using the workbook to explain the details. (I on the other hand had by this point vowed to track down the author and give him a damn good spanking.)
Secondly, he very kindly took some time to explain to me.
I'd noticed that the whole thing expands to an infinite sequence:
> fix f = f $ f $ f ... (fix f)
and he pointed out the similarity between
> ones = 1 : ones
> ones = fix (1:)
and in fact, now that I have my ghci handy, I can indeed confirm that:
> *Main> take 10 $ fix (1:)
> [1,1,1,1,1,1,1,1,1,1]
He pointed out that I could pass the function as a parameter to the fixed subroutine. I sort-of-knew this, in that I remember reading it from WhyOfY, but I hadn't managed to get it compile. Tonight I modified what I'd written to:
> remain f a b = if a < b then a
> else f (a-b) b
(I'd had f f (a-b) b for some reason). And that works:
*Main> (fix remain) 10 3
1
Now, given that Haskell already has recursion and this adds no power or expressivity, and actually just adds noise (the f parameter) and confusion (Huh? How does that even work), I can't see any possible use for this apart from that it's awfully clever. But, though I no longer feel like crying I should probably try to unfold what's happening.
*Main> :t fix
fix :: (t -> t) -> t
As I pointed out, this could be better written as
fix :: ((a->b) -> (a->b)) -> (a->b)
to make it clear that we're fixing a function (except, apparently, you can fix other things too). So fix is passed a function remain which has type
*Main> :t remain
remain :: (Num a, Ord a) => (a -> a -> a) -> a -> a -> a
Meh. I'm lost again. Let's try to unroll it.
> remain f a b = if a < b then a
> else f (a-b) b
So
fix remain = remain (fix remain)
If we were evaluating eagerly that would expand to
fix remain = remain (remain (remain (remain (... fix remain)
But for now it'll stay unexpanded. So.
(remain (fix remain)) 10 3
=> (fix remain) (10-3) 3
=> (remain (fix remain)) 7 3
=> (fix remain) (7-3) 3
=> (remain (fix remain) 4 3
=> (fix remain) 1 3
=> 1
OK. When you expand that lazily, it looks far less insane. I think the visual insanity of
> fix f = f (fix f)
which suggests that the two are equivalent and that it would therefore have to magically find the right value of (fix f) for which an equivalence would hold, really puts you off.
Update: rereading the wikipedia article on fixed point combinators, I liked one part where they compared a fixed point of a simple function, which is a value: like 0 is for add, or 1 is for multiplication. Well, the fixed point for a recursive function isn't a simple value, but another function. I'd originally looked at the definition as if it was an equation, and gone momentarily bonkers thinking “How does Haskell know which value to put in there to make it true!”
I'm going through one of those Blub moments where I just want to dismiss whole swathes of functional programming (in this case, fixed point combinators) as useless and annoying. I guess that's interesting and something to watch out for (I have a sneaky suspicion I will feel like this about plenty of other things along the way.)
(That said, I'd still say that this exercise has no place in that chapter, and probably no place in an introductory textbook at all.)
Later...
> map (\x -> (x+1)/2) xs
First we add the one, then we divide. However the dot doesn't work left-to-right like a pipeline, remember the type-signature Hudak offers is
> (.) :: (b->c) -> (a->b) -> a -> c
So it should be
> map ((/2) . (+1)) xs
> map f (map g xs)
Every element is first mapped with g, and then has f applied. So this should be the same as
> map (f.g) xs
While testing, I still find it odd that a->b->c (alphabetically incrementing) are ordered sequentially too, while f.g is actually applied the wrong way (it ‘should’ be g.f I think).
Now we are supposed to rewrite the earlier example as a map of a map.
> map ((/2) . (+1)) xs
> map (/2) (map (+1) xs) -- using the equivalence above
Here's an example from Chapter 7:
> treeHeightF :: Tree a -> Integer
> treeHeightF = treeF (const 0) maxPlusOne
> where maxPlusOne x y = 1 + max x y
The repeated x y cries out to be simplified. And with a bit of composition, this seems to work > treeHeightF :: Tree a -> Integer > treeHeightF = treeF (const 0) maxPlusOne > where maxPlusOne = max . (1+)
Er, right. That compiles, but I don't understand why, and I have a feeling it may be wrong.
*> let maxPlusOne x y = 1 + max x y
*> let maxPlusOne' = max . (1+)
*> maxPlusOne 0 0
1
*> maxPlusOne 0 1
2
*> maxPlusOne' 0 0
1
*> maxPlusOne' 0 1
1 <--- this is wrong!
OK, so that didn't work. I think my original intuition was correct, and it should have been
*> let maxPlusOne' = (1+) . max
Except that max takes Ord, while (1+) takes Num. I end up trying to make a version of max that takes Num like so:
> max' :: (Num a) => a -> a -> a
> max' x y = max x y
but it doesn't like that. Looking for the diagram in chapter 12 (page 156 in my edition of the book), I see that Num doesn't extend Ord, only Real does. Bah. After lots of faffing about with trying to impose a type of Real in various flailing-about ways, one of the errors vaguely suggests to me that the problem is with the 2 parameters. And in fact
> treeHeightF :: Tree a -> Integer
> treeHeightF = treeF (const 0) maxPlusOne
> where maxPlusOne x = (1+) . max x
actually compiles. Though that can hardly be said to be simpler (a maximum is necessarily of 2 arguments, proposing only 1 is just odd).
This doesn't seem to have worked very well. I'm aware that some of my exercises used the “points free” style alreay and, yes, in some cases its usage is intuitive. But, if you'll permit another Blub moment, sometimes it's just bloody-minded obfuscation to define a function without making obvious what parameters it takes!
I feel a bit guilty about not proceeding with this exercise, given that the example above didn't really work out. But I suppose the “rules” that I'm realising I'm working to are as follows:
I looked at chapter 8 in terror and ran to the (comparative) familiarity of this chapter.
I remember a couple of years ago, when I was looking up Functional Programming early on, I came across the idea that functional programming languages didn't take multiple arguments, but returned a function at each step. I think I scoffed slightly at this idea, which seemed as ridiculous as the idea that my Dad tried to explain once, that Latin didn't usually use personal pronouns.
But all of these funny looking function signatures like
> makeChange :: Int -> [Int] -> [Int]
> -- rather than
> -- makeChange :: ( Int [Int] ) -> [Int]
begin to make sense in the concept of currying.
The explanation of the currying simplification, whereby
> reverse xs = foldl revOp [] xs
> where revOp acc x = x : acc
is by steps turned into
> reverse = foldl (flip (:)) []
is instructive (and slightly terrifying. I mean, just look at that definition!)
> (Polygon pts) `containsS` p
> = let leftOfList = map isLeftOfp
> (zip pts (tail pts ++ [head pts]))
> isLeftOfp p' = isLeftOf p p'
> in and leftOfList
Immediate candidate for simplification is:
> isLeftOfp = isLeftOf p
so possibly
> -- untested
> (Polygon pts) `containsS` p
> = and $ map (isLeftOf p)
> (zip pts (tail pts ++ [head pts]))
The definition of flip given was:
> flip :: (a->b->c) -> (b->a->c)
> flip f x y = f y x
f is a function (a -> b -> c).
flip (flip f) x y = (flip f) y x
flip f y x = f x y
flip (flip f) x y = f x y
-- so
flip (flip f) = f
xs = [1,2,3] :: [Float]
ys = map (+) xs
I suppose we have to know what types the functions involved are:
Prelude> :t map
map :: (a -> b) -> [a] -> [b]
Prelude> :t (+)
(+) :: (Num a) => a -> a -> a
(+) works on the same type o Num a. (+) on a single number will return a function (Float -> Float), so the mapped version should be
> ys :: [(Float -> Float)]
Let's check it out!
Prelude> let xs = [1,2,3] :: [Float]
Prelude> :t map (+) xs
map (+) xs :: [Float -> Float]
OK, so that's [Float -> Float], it seems that the parentheses aren't needed here.
such that
> applyEach [simple 2 2, (+3)] 5
> -- => [14,8]
where simple is defined
> simple x y z = x * (y + z)
> applyEach :: [a->b] -> a -> [b]
> applyEach (f:fs) a = f a : applyEach fs a
> applyEach [] _ = []
which is the definition I made for unmap in Chapter 5. But we can do better than that. If we just swap the item and the list, we can use map:
> applyEach fs a = map apply fs
> where apply f = f a
And of course, if we use the application operator, ($), we can simplify that to
> applyEach fs a = map ($ a) fs
now, as we're swapping the order of parameters, it occurs to me we could so something with flip:
> applyEach = flip applyEach'
> applyEach' a fs = map ($ a) fs
which can be simplified to:
> applyEach = flip applyEach'
> applyEach' a = map ($ a)
which is
> applyEach = flip (\a -> map ($ a))
But I don't know if you can get rid of the remaining parameter somehow.
such that
> applyAll [ simple 2 2, (3)] 5
> -- => 20
Similarly I think this might be a fold. And it has to work such that the input and output types are the same so
> applyAll :: [a->a] -> a -> a
Because we're starting with the initial value, we don't plug it into the apply lexical function, but rather use it as the init argument to foldr.
> applyAll fs a = foldr apply a fs
> where apply f a = f a
Therefore, we can think of simplifying apply by currying:
> where apply f = f
and then I really want to do
> where apply = -- Error!
But funnily enough, that's a syntax error :-) As it happens, we can use the application operator ($) just like above
> applyAll fs a = foldr ($) a fs
Ooo!, and we can do this with a flip, like so
> applyAll = flip . foldr ($) -- dammit, that doesn't work
> applyAll = flip foldr ($) -- neither does that, and it gives a
-- crazy type, that spans multiple
-- lines!
> applyAll = flip $ foldr ($) -- Yay! That's the one.
As you can see, machine gun debugging (inserting and removing operators at random until things compile) is still a preferred technique...
Ah! But actually, though this gives the same result as before, I'm a little doubtful
*Main> applyAll [(+2), (*2)] 4
10
I'd expect it to be 4+2=6 *2=12. The problem will be the use of foldr!
> applyAll = flip $ foldl ($)
But this gives me an error!:
Occurs check: cannot construct the infinite type: b = a -> b
Probable cause: `$' is applied to too many arguments
In the first argument of `foldl', namely `($)'
In the second argument of `($)', namely `foldl ($)'
I'm not sure what's going on here, apart from that it's an example of what Hudak mentions about the choice between foldl and foldr being about a) efficiency and b) sometimes one of the options being “more defined” than the other.
> appendr, appendl :: [a] -> [a] -> [a]
> appendr = foldr (flip (++)) []
> appendl = foldl (flip (++)) []
I'm not sure what this does, so instead of typing it into ghci I'm going to try to work it out first.
appendr [1,2] [3,4]
=> foldr (flip (++)) [] [1,2] [3,4]
Er. Actually, no, I'm confused now. I think foldr op init vs is expecting one further argument (vs), but appendr takes 2. So I try in ghci and indeed it doesn't compile. If I comment the signature line, then it does with the type signature:
*Main> :t appendr
appendr :: [[a]] -> [a]
So let's try again:
let <<++>> = (flip (++))
appendr [ [1,2], [3,4] ]
=> foldr <<++>> [] [[1,2],[3,4]]
=> [1,2] <<++>> foldr <<++>> [] [[3,4]]
=> [1,2] <<++>> [3,4] <<++>> foldr <<++>> [] []
=> [1,2] <<++>> [3,4] <<++>> []
=> [1,2] <<++>> ( [] ++ [3,4] )
=> [1,2] <<++>> [3,4]
=> [3,4] ++ [1,2]
=> [3,4,1,2]
Perhaps this would be clearer with 3 elements?
appendr [ [1,2], [3,4], [5,6] ]
=> [1,2] <<++>> ([3,4] <<++>> ([5,6] <<++>> []))
=> [1,2] <<++>> ([3,4] <<++>> ([] ++ [5,6]))
=> [1,2] <<++>> ([3,4] <<++>> [5,6])
=> [1,2] <<++>> ([5,6] ++ [3,4])
=> [1,2] <<++>> [5,6,3,4]
=> [5,6,3,4] ++ [1,2]
=> [5,6,3,4,1,2]
appendl [ [1,2], [3,4], [5,6] ]
=> (([] <<++>> [1,2]) <<++>> [3,4]) <<++>> [5,6]
=> ([1,2] ++ []) <<++>> [3,4]) <<++>> [5,6]
=> ([1,2] <<++>> [3,4]) <<++>> [5,6]
=> ([3,4] ++ [1,2]) <<++>> [5,6]
=> [3,4,1,2] <<++>> [5,6]
=> [5,6] ++ [3,4,1,2]
=> [5,6,3,4,1,2]
From the discussion in Chapter 5, we see that concatenating with (++) takes time proportional to the number of elements in the left-hand list. appendl repeatedly concatenates the left hand side of the list, so should be slower. (Though in this case, appendr scores 0+2+4=6, while appendl scores 2+2+2=6, which is equal).
> (twice (+1)) 2 => 4
That's easy enough:
> twice :: (a->a) -> a -> a
> twice op v = op (op v)
Now, what does twice twice do? I have no idea, given that twice takes a function (a->a) while twice itself isn't such a function. Or... maybe it is if you read it as (a->a) -> (a->a).
Here, my notes show that I am confused, as I make notes such as “GRAAAH” and “WTF?” as well as going through the (.) and ($) options again:
*Main> :t twice twice
twice twice :: (t -> t) -> t -> t
*Main> :t twice $ twice
twice $ twice :: (t -> t) -> t -> t
*Main> :t twice . twice
twice . twice :: (t -> t) -> t -> t
The end result of this confusion was that twice op returns a function of the same sort as required for twice, so twice twice should simply do the operation 4 times. And twice twice twice will do it 16 times.
what about “twice(twice twice)“ I would think that would be the same as “twice twice twice”, and in fact it is (though perhaps there are efficiency concerns again)
> power (+2) 5 1 => 11
> power :: (t->t) -> Integer -> t -> t
> power f n init
> | n==1 = f init
> | otherwise = f (power f (n-1) init)
> twice :: (a->a) -> a -> a
> twice f = power f 2
Now, to define something useful... I suppose we can do multiplication, though to be honest it seems a bit naff:
> mult x y = power (+x) y 0
The second half of this chapter is quite tricky, and I'm tired, so I'm going to break off here.
Just a quick post as I've not had a lot of time to play with Haskell just recently.
This morning I noticed Jonathan Lang's post to perl6-language asking if the ternary operator ?? !! could be turned into two binary operators. I thought this had been discussed some time back, but apparently not. Audrey commented that his suggested solution might not work for cases where the condition is true but the result value is untrue. I wondered if Perl 6's "hypothetical variables" (which might or might not contain a value) could be used. In that case, you could make ?? bind the hypothetical variable if the Left Hand Side is true, and not otherwise. !! would then become one of the list of short-circuiting OR operators.
|| # truth
// # definedness
!! # "boundness"
I then had a snap of inspiration that it could be done in Haskell with the Maybe monad and knocked up the following (using ? ! because !! is already taken for list indexing)
True ? a = Just a
False ? _ = Nothing
Just a ! _ = a
Nothing ! b = b
Which seems to give the expected results
*Main> True ? "Bill" ! "Ben"
"Bill"
*Main> False ? "Bill" ! "Ben"
"Ben"
I start off confidently, typing in the first example into my scratch file:
> data Tree = Leaf a | Branch (Tree a) (Tree a)
Of course, ghci complains bitterly, and strangely
Prelude> :l 7.hs
[1 of 1] Compiling Tree ( 7.hs, interpreted )
7.hs:5:19: Not in scope: type variable `a'
7.hs:5:36: Not in scope: type variable `a'
7.hs:5:45: Not in scope: type variable `a'
Failed, modules loaded: none.
Eventually I realise I started off a little too confidently and left out the parametrised variable...
> data Tree a = Leaf a | Branch (Tree a) (Tree a)
I'm trying to practise my syntax by reading the definitions of the functions (mapTree, fringe) etc., and then writing them out before compiling and checking in the book. As it happens I've previewed them before, but at least this helps get the syntax into my head!
I'm still finding the error messages hard to read:
7.hs:13:27:
Couldn't match expected type `a' (a rigid variable)
against inferred type `[a]'
`a' is bound by the type signature for `fringe' at 7.hs:11:19
In the expression: fringe x
In the first argument of `(++)', namely `[fringe x]'
In the expression: [fringe x] ++ [fringe y]
This is because the expression at the bottom should have been
fringe x ++ fringe y
as fringe already returns a list.
I thought I'd test the functions and tried it out
*Tree> fringe t
<interactive>:1:7:
Couldn't match expected type `Tree a'
against inferred type `Tree Integer -> Tree Integer'
In the first argument of `fringe', namely `t'
In the expression: fringe t
In the definition of `it': it = fringe t
Which I thought was odd. Where was the “Tree Integer -> Tree Integer” coming from?
*Tree> :t t
t :: Tree Integer -> Tree Integer
I tried constraining the definition of my tree, t:
> t :: Tree Integer
> t = Branch (Branch (Leaf 2) (Leaf 3))
Which of course gave a similar error, and I eventually realised that I'd missed off the second branch...
> -- much better
> t = Branch (Branch (Leaf 2) (Leaf 3)) (Leaf 4)
What can I say, it's been a long day at work... Anyway, with a structure like this I can play with the functions
*Tree> fringe $ mapTree (*2) t
[4,6,8]
Are there commonalities that can be abstracted out, like they were when we developed fold?
> fringe :: Tree a -> [a]
> fringe (Leaf x) = [x]
> fringe (Branch x y) = fringe x ++ fringe y
> treeSize :: Tree a -> Integer
> treeSize (Leaf _) = 1
> treeSize (Branch x y) = treeSize x + treeSize y
I looked at this stupidly for some time thinking “But the bit that handles the leaf isn't the same function as the one that sums together the branches!” and then eventually realised that modern functional programming languages can probably handle more than one functional argument...
I came up with
> -- a new Higher Order Function for trees??
> treeF :: (a->b) -> (b->b->b) -> Tree a -> b
> treeF f o (Leaf x) = f x
> treeF f o (Branch x y) = (treeF f o x) `o` (treeF f o y)
Which would then be used with functions like
> fringeF :: Tree a -> [a]
> fringeF = treeF list (++)
> where list x = [x]
> treeSizeF :: Tree a -> Integer
> treeSizeF = treeF one (+)
> where one _ = 1
which, incredibly, works! The formulation for treeHeight is a bit uglier:
> treeHeightF :: Tree a -> Integer
> treeHeightF = treeF zero maxPlusOne
> where zero _ = 0
> maxPlusOne x y = 1 + max x y
{
Parenthesis on const: I don't like having to create little lexical stubs to give the literal 0 and 1 above. In Perl you would just do sub {1} for example, which made be think of a lambda: (\_ -> 1) which is hideous. Now if only there was a function that threw away one of its arguments. I got as far as defining it
*Tree> let _ & a = a
*Tree> map (&1) [2,3,4]
[1,1,1]when I remembered that I'd seen it in the prelude. It's a bit less compact than my operator version, but it is called “const”, which makes sense. So now we can write
> treeHeightF :: Tree a -> Integer
> treeHeightF = treeF (const 0) maxPlusOne
> where maxPlusOne x y = 1 + max x y}
And, the definition of mapTree was written more intuitively than rationally - I can barely believe that it works:
> mapTreeF :: (a->b) -> Tree a -> Tree b
> mapTreeF f = treeF mapLeaf Branch
> where mapLeaf x = Leaf (f x)
See that?! The two things that abs