1. In which a challenge is thrown, but there is a spanner in the works!

Haskell suddenly became “important” in the Perl community when Audrey Tang started to blog about Pugs, the prototype version of the Perl 6 interpreter/compiler. So, when I started looking at Haskell, I did so with another Perl-monger, larsen, one of the key guys in perl.it. We worked through some of the exercises in YAHT together when we shared a flat. Since I moved out we never really got around to doing that, and I've been working through the exercises in SOE on my own. I realised that the poor chap was missing out on all the fun! So I thought I could let him “catch up”, but as that would involve having to give up my precious copy of “Haskell School of Expression” up, even for a few days, I panicked slightly.

My alternative was almost a stroke of genius. For a couple of months I've had “Practical Common Lisp”, which larsen lent me, on my bookshelf. I even read some of it! But I've not gone through in any rigorous way. My challenge to him was to do what I'm doing with SOE and to blog the exercises.

The “concept” is that at the end of it, I will be able to teach him Haskell, and he can teach me Lisp. If you need to know both to be a truly great programmer, perhaps we can both at least be half of one of those!

The flaw, as it happens, would seem to be that PCL doesn't have seem to have exercises... (though we seem to remember them existing somewhere, this was only on a brief scan).

2. In which osfameron squees at slime, and criticises the Perl debugger and REPL

He has already downloaded SLIME, and mentioned how cool the video with Marco Beringer was. I hadn't seen it so he passed me the link. It is rather nifty, and certainly you can see how features of Lisp like its regularity make it a joy to parse and manipulate in an IDE. Other things, like the incremental compilation are interesting, and the depth of debugging information is astounding.

Compared to this, perl -debug comes off rather badly. Actually, compared to a drunken, syphilitic stoat, the Perl debugger might come off badly, but the SLIME package is really rather well put together. The Perl REPL has several disadvantages, such as not understanding lexical scopes and not printing out the results of each call. The cry of “it's hard to use” is probably just an excuse, after all, if a tool's worth using, you put time into learning it. The suspicion though is that the Perl debugger isn't really worth learning. Certain things add to this conviction: for example, I had a vivid memory that Larry Wall had declared that he was more of a “print statements kind of guy”. (But, not I can't find it via Google, perhaps I dreamt it). In any case, there is the fact that generally, Perl programmers, if they even know about the debugger, tend to use it only for the REPL (and then moan about it).

At some point, Acme did some work on improving the debugger internals, documentation and test-suite while creating Devel::ebug, which looked very cute. In theory at least: I could never get it to install, and I believe it's now unmaintained and targetting an outdated version of Catalyst. (Some time passes... some facts are checked...: eeek! No, there have been 2 releases over the last couple of months, yay Acme! And my colleague Mattia Barbon submitted patches, yay Mattia! I guess I'll have to check it out again at some point).

Anyway, Lisp absolutely has an impressive toolchain. But the aesthetic appeal (and, yes, I know that this is influenced by a lack of familiarity) is still lacking - all those #\UPPER-CASE-SYMBOLS, especially on the stack traces. Meh. Yes, I know this is stupid, but it is odd that a language whose algorithms and concepts are so beautiful should look so fugly.

(Of course, I find (well written) perl code pleasant to read, so I may not be qualified to pronounce on the aesthetics of programming. OTOH, this Larry Wall quote I do remember (and Google confirms that I didn't dream it) “Lisp has all the visual appeal of oatmeal with fingernail clippings mixed in”.)

3. In which osfameron ponders the virtues of Perl as a functional programming language, and sings the praises of join

Since the publication of Dominus's seminal Higher Order Perl, it's hard to deny that Perl enables some Functional Programming techniques (though you can certainly argue that some of the techniques are uglier, harder, or less efficient). The three functions in common use are map, grep, and join.

When Marco creates the convert-to-morse function, he started by writing a stream to a string, (nice technique! see also IO::Stringy etc. in Perl) prints a morse character for every character, followed by a space. He then points out that there's a spurious space after the last character.

He then starts musing about how to get rid of this and ends up dealing with the head of the string first, and then doing the rest of the string, this time prepending the space. While he starts doing this, every Perl-programmer's muscle in me is screaming, “use join you fool!”

Anyway, he may be doing it this way for pedagogical purposes, but his solution surprised me nonetheless. And while I was thinking about it, I noticed that I hadn't come across join in Haskell either yet, so I decided to write it.

First of all, I thought it would be:

  > join j = foldr (\left right -> left ++ j ++ right) [] 

which compiles like so

  *Main> :t join
  join :: [a] -> [[a]] -> [a]

But there is a problem

  *Main> join "," ["hello","world"]
  "hello,world,"

A final comma! Of course as the list is really (“hello” : “world” : []) the fold will join “world”,”“. Pesky blighter.

I ended up with the slightly less beautiful:

  > join j (v:[]) = v
  > join j (v:vs) = v ++ j ++ join j vs

with the same signature. (We could also do join [100] [[1,2], [3,4,5] for example).

What is the standard Haskellish way of writing join?

(Update: dons on #haskell suggested that the obvious name for this in haskell is "intercalate".  Actually intercalate (so named, because "join" is already taken - for joining monads) would work.  intercalate would be defined as the concatenation of "intersperse".  Steven Ashley suggested this solution too.  (Update: and dcoutts in irc backlog, thanks all!)

    concat $ intersperse "," ["hello", "world"]

on a related note, while I'm hating crappy REPLs, why does ghci make it so bloody hard to do "import Data.List" (in order to get intersperse)?  Interestingly, Perl (5) doesn't have intersperse, as "join" only operates on strings, and it would be nice if it did have the generalised version too.)

4. In which a better REPL for Perl is sighted, and osfameron bemoans the lyf so short

This morning, via a cpanranting on Rocco Caputo's Lexical::Persistance, I came across Matt Trout's new-ish Vox blog. As well as an interesting polemic about Ruby, there's a series about developing a REPL (called Devel::REPL, not yet on CPAN but it's on his bast repo, linked from the blog), which uses that module to allow variables like my $foo to persist from one line in the REPL to another. Just like they should!

mst also talks a lot about Moose, the new Perl object framework which is massive news in a subset of the modern Perl community. It's quoted as bringing to Perl the things that you would otherwise have to flee to Ruby for. Things like declarative class generation and function argument unrolling (in an extension iirc). And (as this post is already too long), “much much more”.

All of which reminds me that, as well as spending time learning Haskell, I should really keep up to date with learning Perl. Which I will obviously do in my proverbial Copious Free Time!

I whined on IRC about my inability to do simple trig and dakkar kindly took me through the basics of a cosine. So I sat down later to look again at an exercise I'd skipped: 2.2 to defined the function:

 > regularPolygon :: Int -> Side -> Shape>

But I realised that I still couldn't remember what I was doing and so consulted Wikipedia's handy page on trigonometry. Armed with Cos A = adjacent/hypotenuse I knocked together

 > regularPoly :: Int -> Float -> Shape
 > regularPoly nsides r = Polygon $ _poly 
 >       where _poly :: Int -> [(Float,Float)]
 >             _poly side
 >                 = let frac  = 1 / fromIntegral nsides
 >                       xyRay :: Int -> (Float,Float)
 >                       xyRay side =
 >                         let ratio = frac * fromIntegral side
 >                             rad = ratio * 2*pi
 >                             adj = cos rad * r
 >                             opp = sin rad * r
 >                         in (adj, opp)
 >                   in if side == nsides then []
 >                      else xyRay side : _poly (side+1)

OK, so this is certainly baby-Haskell, but I was quite pleased with it. I'm liking let clauses, which is interesting, coming from Perl 5 where lexical subs don't exist and so I never saw the need for them before. I'm finding that where clauses have slightly different scoping rules (I had to move the definition of xyRay into a let as it didn't work as a where. Then I realized that _poly on the other hand would work in a where as well as a let).

To check if it worked, I plugged it into the code for chapter 4, first of all forgetting to add regularPoly to the list of functions exported by Shape.hs. The function works fine, though I've realised now it's not to specification - it takes a “radius” rather than the length of the side. Sigh, I'll come back to that problem later.

... (some time later)

The line AB is of length s, which is how the input is specified. We're using r instead. Bisecting the line, we have 2 triangles with perpendicular sides s/2 and r. The angle AOB is of 360/n where n is the number of sides. So AOC is 180/n. Using the tangent identity:

 >   tan 180/n = s/2 / r
 >   s = 2r * tan 180/n
 >   r = s/(2 * tan 180/n)

So in Haskell, we can define a facade on regularPoly like so:

 >   -- #sides -> side -> Polygon [(x,y)]
 >   regularPoly2 :: Int -> Float -> Shape
 >   regularPoly2 nsides s = regularPoly nsides r
 >       where r = s / (2 * tan (pi / fromIntegral nsides))

Then of course, on IRC, Apocalisp showed his version of it which is significantly more beautiful, and which uses the clever idea of rotating a point an infinite number of times and then take‘ing from it. I asked permission to post it here, which he gave, but then told me that there was a bug in it for larger polygons, which could just be to do with floating point precision so he was proving it correct first. Which is the kind of rigour that I'm quite manifestly lacking.

I have an up-to-date version of his code now, but I think I'll do a proper analysis of his and David's versions of a couple of answers and possibly (eeeek!) try to prove them correct/equivalent.

This is an interesting chapter, working on the higher order functions rather than actually drawing shapes.

It covers:

• Polymorphic types
• Principal type - this is an interesting idea, the type inferencer can determine that something works on an Int, say, or “Number stuff”, or “just any stuff”, or “a list of stuff”. Too general and it's no longer useful. The principal type is the most general type determinable for the function that is still useful.
• map, yay! (OK, so Perl isn't well known as a functional programming language, though see Dominus's Higher Order Perl, but at least map and grep (filter I think in Haskell) are well within my comfort zone.
• This is quite cute: sequence_ (map aux css). i.e. you can use map for actions too.
• Implementing “append” - fixity is important consideration, e.g. whether left associative or right associative
• One of the things that always baffled me with the definition of fold was why you needed an init argument at all. It just seems clumsy to be doing foldl (*) 1 or foldl (+) 0 when you could just use the first item of the list and get the same result.

  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.

• The extended example of how to implement reverse example is nice. I found it quite tricky to read at first, but following through it, it begins to make sense.
• Error handling (briefly)
• I like the definitions for (&&), (||) :: Bool -> Bool -> Bool

Ex 5.1 Rewrite the equation for the area of a polygon given in Section 2.2. in a higher-order, nonrecursive way, using operators such as map, fold, and so on.

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)

Ex 5.2 What is the principal type of each of the following expressions

• map map
• foldl foldl
• map foldl

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.

Ex 5.3. Rewrite the definition of length nonrecursively

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.

Ex 5.4

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.

Exercise 5.5.: define functions that do various things...

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.

Ex 5.6. defined maxList that computers the maximum element of a list.

  *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?)

Ex 5.7 Function to add “pointwise” elements of a list of pairs

  *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)

Ex 5.8 Create an encryption function for frogs

 >  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

5.9 define makeChange such that

  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!)

We are presented with some coercion functions and asked

Ex 4.1: Why is inchToPixel x not defined as 100 * round x ?

It is instead defined as round(100 * x). This is because if rounding was done on the input parameter, then whether it was, say, 1.01 or 1.99, the answer would be the same: 100*(round 1.01) = 100*1 = 100.

Ex 4.2 Why is pixelToInch n not defined as intToFloat (n/100)

Similarly, this is to do with fixity/order of application of expressions: The version above would first try to evaluate n/100, which will fail, as n is an Integer, and “/“ isn't defined for Ints.

That's it for the exercises. I played along with the examples, which basically amounts to copying out of the book - actually I think that's more instructive than just reading or getting the source code off the internet, because it helps develop finger-memory.

Well, he does leave a “you may wish to define these functions on your own as an exercise”, but right now, I'm going to bed instead.

David Tran got in touch to say he's also working his way through SOE, and he's posting on http://davidtran.doublegifts.com/blog/, where he's mainly posting solutions, looks good!

I discussed some answers on irc with Apocalisp, who has some very subtle versions of regularPolygon and isConvex.  I may, though I still find doing proofs painful-and-not-really-fun try to work through the proofs that our versions are equivalent.  Maybe.

I recently discovered that some of our new colleagues from Splinder are Erlang programmers and are working with ejabberd etc.!  I've subscribed to Loreto's blog (in Italian) as Erlang is next on my list of things to learn.

While I was looking for information about Erlang, I found the LinkedIn group about it and requested to join.  Martin Logan who is an admin for the group emailed me with a proforma email including... an Erlang syntax question.  I considered googling the answer but thought I'd be honest... so I confessed that I was interested in learning it, which he seems to be satisfied with.  So I'm now a member, although I can't figure out how to get LinkedIn to do anything with that (is there a group page?  a list of members? a blog?)

HTML is all very well and good, but frankly, I'm too lazy to mark up my
&,<,> characters all the time by hand, at least within
code.  I used the POD formatter pod2html for a couple of early
posts.  It's OK, it basically has a concept of "This is a normal text
paragraph, and this is a code paragraph" but for those times that I
want to do anything clever, it's just that little bit more clunky than
markup in HTML.

When I asked what people use on IRC, people suggested HsColour.  OK,
that wasn't really the question - I was more about laziness and
practicality than shiny features - but, fair enough, highlighted haskell
code would be nice too.

I had a stupid little formatter I use for fiction writing, which does
basic paragraph formatting and word count, while making a horrible hack
of not screwing up HTML markup (because it, er, "grew organically", and
I didn't get around to using an HTML parser as I would have done if I
were sane).

So I hacked on the Perl (yeah, not haskell, this is a blog on learning
haskell, if I already knew how to write the formatter in it...) doing
the following

• Bringing it into my ‘modulino’ framework (which handles things like
  command line options, documentation, logging etc.)
  
• reworking the parsing to be more modular so you can subclass it
  easily
  
• using HTML::Parser instead of just hacking at it with
  regexps.  (The smartquote stuff is still regexps of course)
  
• adding a rule for indented paragraphs, and haskell paras (indented
  with the first nonwhitespace character being ">".   This uses
  HsColour -partial -html
  

If I found the exercises in chapter 2 a little hard, the fact that there
are only two of them in this chapter should have been a warning...

Amusingly, Hudak suggests that the module SOEGraphics will not
evolve, as it is designed for the textbook, however, as it happens, it
has changed its API in a significant way - by being renamed to
Graphics.SOE.

The chapter starts explaining “actions” and how we'll do IO with them.
The explanation is clear, and doesn't mention the magic and terrifying
word “Monad” once.

We learn how to do “Hello World”!  He briefly mentions commands like
readFile, getLine, writeFile, but we're
concentrating on graphics here, so not going to go into that much
detail.

The example of creating putCharList by sequence_ing a
group of putChar actions is very odd and intriguing.

And then we move onto a graphics example!  The first time a do
expression is seen, and in my edition the code listing spans pages 40
and 41, with the opening “do“ being just before the page break,
so it's easy to get the alignment wrong.

(Although, to be fair, he does mention alignment the page before and the
rules are the same as the “let“ and “where“ clauses
we've already used).

ex 3.1 Defined putStr and getLine “recursively”, ie. not as a sequence_ of mapped actions.

The hint says to use “return“ like the preceding discussion, which
appears to be very brief - though I said the IO discussion was clear,
I'm not sure it really explains what "return" does in the detail
necessary to understand this exercise.

With a bit of playing putStr seems to be definable something like this:

 > putStr2 :: String -> IO ()
 > putStr2 [] = return ()
 > putStr2 (s:ss) = do putChar s
 >                     putStr2 ss

You can do return () :: IO () instead, as per his hint, but it
doesn't seem to be necessary.

Though that seems to work, it's interesting observing myself trying to
get to that point, basically flailing around at random till I find
something that ghci will compile.  This was even more evident
for the getLine example.  I'm trying to create an auxiliary
function _getLine2 which will do the looping, and I'm getting errors
like

 Couldn't match `[Char]' against `a -> IO a'

Which reminds me that I should be thinking this through rather
than trying to work it out intuitively.   Without the auxiliary function
I can get as far as:

 >    getLine2 :: IO String
 >    getLine2 = do x <- getChar
 >                  if x == '\n' then return "" :: IO String
 >                               else  ...

but at that point I really want to get the char returned from getChar
and then recurse into getLine2 again, concatenating the result.  But
that means running yet more IO commands, and I'm unsure as to how to do
that in Haskell syntax.  I tried:

 >    getLine2 :: IO String
 >    getLine2 = 
 >        do x <- getChar
 >           if x == '\n' then return "" :: IO String 
 >                        else y <- getLine2; return (x : y) :: IO String

which complains with the helpful “Parse error” (Haskell error reporting
is surprisingly underwhelming.  Say what you like about my main
language, Perl (and, yes, most people do...) but it has surprisingly
helpful and useful error messages compared to anything else I've seen.)

Adding a do:

 >    getLine2 :: IO String
 >    getLine2 = 
 >        do x <- getChar
 >           if x == '\n' then return "" :: IO String 
 >                        else do y <- getLine2; return (x : y) :: IO String 

works though.  (I was sure I'd tried this before).  As I said, until I
understand this, this kind of flailing around adding stuff at random is
probably the order of the day, and I don't think that the discussion in
the book about this topic was really enough to be able to realistically
do that much else.

Ex 3.2.  Draw a snowflake fractal!

On the face of it, with the good examples on drawing a triangle, this
exercise ought to be easy in comparison!

OK, first of all, there is the maths fun of how to work out where the
triangle points go.  I started messing about with a bit of pythagoras,
and ended up deciding that I'm too stupid to work this out, so let's
just work out some likely looking constants to multiply “s“ by,
and we should be ok.  (But I will at some point look up the maths to do
this properly - I was guessing that with a bit of pythagoras and some
equations I'd be able to get there, but I appear to have forgotten
everything I studied 12 years ago and just can't do it)

At this point haskell bites me in the arse with Integers.
fromInteger takes an Integer, whereas polygon takes Ints.  This
is obviously time to kick cute small fluffy creatures.

Sneaking ahead a few pages to chapter 4, we see the definition

 >    intToFloat :: Int -> Float
 >    intToFloat n = fromInteger (toInteger n)

Which helps.  (quicksilver on #haskelll pointed out that there is a
function fromIntegral).  Eventually, I'm able to create the
snowflake generator!  To add the withColor, I end up passing a list,
threading it through (in the way that I'm beginning to understand that
Monads will help me with when I understand them...), and using a bit of
cleverness with a repeated lazy list:

 > main
 >   = let colors = cycle [White,Blue,Yellow,Red,Green]
 >     in runGraphics (
 >         do w <- openWindow "Snowflake" (800,900)
 >            star w colors (350,350) 280
 >            spaceClose w
 >         )

I started off with concat . repeat, but quicksilver pointed me
at cycle, which to be honest is more readable.

 >    star :: Window -> [Color] -> (Int,Int) -> Int -> IO ()
 >    star w (c:cs) (x,y) s
 >        = let t1 = triangle (x,y)   s
 >              t2 = triangle (x,y) (-s)
 >              points = t1 ++ t2
 >              aux (x',y') = star w cs (x',y') (s `div` 3)
 >          in do drawInWindow w (withColor c $ polygon t1)
 >                drawInWindow w (withColor c $ polygon t2)
 >                if s > 2 then sequence_ (map aux points)
 >                         else return ()

Again, quicksilver suggests mapM_ instead of sequence_ .
map.

Update: Though I used the definition of intToFloat in the
original version of the triangle routine, (multiplying likely looking
constants by the side argument, because I didn't get the maths to draw a
proper equilateral triangle) I now implemented regularPoly
so I just used that.  The small matter that the Shape constructors take
Float while we're using Int is why I ended up using truncate:

 > triangle (x,y) s
 >  = let poly2list (Polygon p) = 
 >        map (\(x1,y1)->(x + truncate x1, y + truncate y1)) p
 >    in poly2list (regularPoly 3 (fromIntegral s))

This actually works!  I think the Graphics.SOE library may be both slow
and buggy though due to:

• It's observably slow.  I'd expect the whole fractal to be drawn
  near instantly.  Or at any rate faster than the very leisurely rendering
  I'm getting.
  
• sometimes rendering just stops until an IO even happens.  If I move
  the mouse pointer over the window then the rendering picks up.
  ghci regularly moans “thread blocked indefinitely”.
  
• If I necessitate even a partial redraw of the window (for example
  if another window obscured a section of this one), then on redraw the
  whole fractal is drawn again (slowly), and sometimes twice.
  

Is this how Graphics.SOE works?  If so, I'd say it isn't
particularly impressive, though to be fair it is a sample library for
pedagogical purposes.  Of course, it's likely that the problem lies with
my implementation.  Comments welcome!

And here's the snowflake!

Hello Planet

A couple of weeks back, I got an email from Antti-Juhani who'd just processed
my request to have this blog added to planet Haskell.  He pointed out
that I seemed to have gone awfully quiet...  Basically, not had a lot of
tuits recently, but now I'm working through SOE a bit more seriously,
here are my notes on Chapter 2, I've drafted 3-4, will post ``soon'',
hopefully.

---

Chapter 2: A module of Shapes, Part 1

Already by chapter 2, Hudak starts showing us interesting things with
shapes and the power of haskell's types.  We start by defining a module.

 module Shape () where
    data Shape = Circle Float
               | Square Float

I played along in ghci, the interactive interpreter, which is very
handy and fast.  I started by loading the code using :l Shape.hs,
which worked fine.  Then, I could easily check the type of Circle and
Square:

 *Shape> :t Circle
 Circle :: Float -> Shape

Though... :t Shape it doesn't like on the other hand.

2.1

The next version, with improved constructors works too, though you have
to notice that deriving Show is indented because it's part of the
definition of the datatype Shape.

The next version is also cute - instead of saying that a datatype is in
measurements of Float, say it's a Side (which is equivalent to a
Float).  This seems quite powerful and pleasing.

 *Shape> :t Ellipse
 Ellipse :: Radius -> Radius -> Shape

of course :t Radius doesn't work.  Checking ghci's help, there
is another command, :k to show ``kind'' of type.  This gives ``*''
for both Radius and Shape.

Hudak then shows how to define functions like

 square s = Rectangle s s

which works fine.

 *Shape> :t square
 square :: Side -> Shape
 *Shape> square 2
 Rectangle 2.0 2.0

Exercise 2.1: define functions rectangle and rtTriangle in terms of Polygon

 rectangle s1 s2 = Polygon [(0,0), (s1,0), (s1,s2), (0,s2)]

Though later in the text Hudak shows polygons centered around 0, in
which case we'd want something like (using let expressions and hoping
that I've understood the whitespace formatting rules)

 rectangle s1 s2 =
    let s12 = s1 / 2
        s22 = s2 / 2
    in Polygon [(-s12,-s22), (s12,-s22), (s12,s22), (-s12,s22)]

Woot!  Which appears to work.

The triangle should just be:

 rtTriangle s1 s2 = Polygon [(0,0), (s1,0), (0,s2)]

Exercise 2.2: Define a function regularPolygon :: Int -> Side -> Shape

Eeek!  ``Consider using trigonometric functions'' like sin and cos.
I actually liked Maths at school.  Then I studied Literature
at University, and do I remember anything?  OK, let's check this out,
I seem to remember either sin 90 or cos 90 as being 1.

 *Shape> sin 90
 0.8939966636005579
 *Shape> cos 90
 -0.4480736161291701

This may have something to do with degrees and radians.  Which I don't
remember ever learning in school...  But it has something to do with PI

 *Shape> cos pi
 -1.0
 *Shape> cos (2*pi)
 1.0

I have no idea why the functions sin and cos default to radians, and why
this isn't even mentioned, as if anyone even knew what radians were,
bah.

I don't think I'm in any shape (no pun intended) to attempt this
exercise.  When I'm online I'll google a basic tutorial on trig.

Section 2.2

The pattern matching stuff is cool, though at this level of explanation
it looks pretty much like method overloading in Java say.

The function for calculating the area of a convex polygon is quite
cute, it seems rather a complicated function to think of creating by
yourself at this stage (and in fact it's just presented on a plate in
this instance).  The second version, with a lexical subroutine
polyArea in a where clause makes my head hurt slightly.  Basically,
it's to avoid having to create a new Polygon object each time, though of
course the list of vertices that would have created the polygon still
exists.  I like that the inner lexical sub refers to variables declared
in the outer sub (my main language, Perl, doesn't have lexical subs
other than anonymous closures).

Eeeek!  Whitespace!  It is not unknown for Perl programmers to look with
pity or scorn at Pythonistas and their strange whitespace rules.  The
Haskell ones seem particularly crack-fuelled as described, though I'll
grant that they seem to make for very nicely formatted source code.
(And at least you can use braces and semicolons if you really want to).

Exercise 2.3 Prove a property...

Eeek!  More proofs.  Well, I said I would give this a go instead of just
grimacing and skipping, so here goes.

Prove that:

 area (Rectangle s1 s2) 
   => area (Polygon [(0,0), (s1,0), (s1,s2), (0,s2)])

Given that I just went ahead and implemented the function
rectangle as that, I obviously believe this to be true.  I
guess that Hudak's point is that there is a) some safety, and b) some
insight in actually knowing this.

• From one side
  
  

  
   area (Rectangle s1 s2) = s1 * s2

  
  
• And from the other
  
  

  
   area (Polygon [(0,0), (s1,0), (s1,s2), (0,s2)])
      = polyArea [(s1,0), (s1,s2), (0,s2)]
      = triArea (0,0) (s1,0) (s1,s2)
          + polyArea ((s1,s2) : [(0,s2)])

  
  
• unfold triArea
  
  

  
   a = distBetween (0,0)   and (s1,0)  = s1
   b = distBetween (s1,0)  and (s1,s2) = s2
   c = distBetween (s1,s2) and (0,0)   = sqrt(s1^2 + s2^2)
   s = 0.5 * ( s1 + s2 + sqrt(s1^2 + s2^2))

  
  
• so
  
  

  
   triArea = sqrt( s * (s - s1) * (s - s2) * (s - sqrt(s1^2 + s2^2)))

  
  

At this point, I'm beginning to lose it, so I peek back at Hudak's
proof of the RtTriangle area.  He notes that

 s * (s - lengthOfHypotenuse)
      => 0.5 * s1 * s2

 (s - s1) * (s - s2)
      => 0.5 * s1 * s2

Which is nice.  (My maths muscles are flabby, I'm just going to take
that as a given now)

• so
  
  

  
   triArea = sqrt( (0.5 * s1 * s2) * (0.5 * s1 * s2) )

  
  

  As the two expressions are the same...

  
  

  
   triArea = 0.5 * s1 * s2

  
  
• so
  
  

  
      polyArea rectangleVertices =
          0.5 * s1 * s2
        + polyArea [(s1,s2), (0,s2)]

  
  

  This is pattern matched by polyArea (v2 : v3 : vs') with vs'
  matching the empty list.  This time, we need to work out the triangle
  area

  
  

  
    triArea (0,0) (s1,s2), (0,s2)

  
  

  Which is exactly the same form as above, and which will also resolve to

  
  

  
    0.5 * s1 * s2

  
  
• and
  
  

  
      polyArea rectangleVertices = 
          (0.5 * s1 * s2)
        + (0.5 * s1 * s2)
        + polyArea [(0,s2)]

  
  

  polyArea [(0,s2)] can't be matched against (v2 : v3 : vs') so it
  returns the default 0 instead.

  
  
• and finally
  
  

  
    polyArea rectangleVertices = 
          s1 * s2

  
  

Phew!  I have scheduled remedial Maths as the next thing to (re)learn
after Haskell.

Exercise 2.4

Define a function  convex :: Shape -> Bool
For the non polygon ones, the shape is always convex.

    convex :: Shape -> Bool
    convex (Rectangle  _ _) = True
    convex (Ellipse    _ _) = True
    convex (RtTriangle _ _) = True

I wonder if we can just set a default?

    convex :: Shape -> Bool
    convex _ = True  -- default for all non-polygon shapes

Woot!  Now for polygons!  Which is where I get stuck.  I think that we
can tell that it's convex if all the vertices turn in the same direction
(clockwise or anticlockwise)  All I need to do is to:

a)

know which function to iterate all the vertices, 3 at a time (I think
I'm thinking of zipWith3, from a few advance peeks elsewhere) I
suppose this could be done recursively, like the polyArea definition.

b)

have a function that will tell me if 3 points are clockwise or
anticlockwise

c)

tell if all the vertices are clockwise or anticlockwise

This all seems rather complicated.  I'm not even sure how to tell if the
3 points turn clockwise or anticlockwise.  Trig?  Or maybe just seeing
if the 3rd point lies to left or right of line defined by first two.
(Which from peeks, I know is a function defined later on).

I gave up on this exercise, then discussed on #haskell with fasta who
gave some suggestion on doing it with explicit recursion.  (At this
stage in the book, we haven't touched higher order functions and I think
it's a good exercise to try this way).

So, with a bit of encouragement/taunting from fasta, I gave it another
go, it should now identify anticlockwise polygons correctly as concave
or convex.

(It is hardcoded to work anticlockwise, I could presumably check the
first direction, and then have the outer function test that the
subsequent vertexes are still in that direction)

    convex:: Shape -> Bool

    convex (Polygon (v1 : v2 : v3 : vs)) 
        = _convex (v1 : v2 : v3 : vs ++ [v1,v2])
        where _convex   :: [Vertex] -> Bool
              _convex (v1 : v2 : v3 : vs)
                    = turnedLeft v1 v2 v3 && _convex (v2 : v3 : vs)
              _convex _ = True -- base case, for example 
                               -- a point or a line is convex

    convex _ = True  -- default for all non-polygon shapes

    -- "which way did we turn?" function from page 95, slightly modified
    -- (I tried to do the maths of this, and got caught up with
    -- gradients and intersection points.
    -- this property seems rather random, I guess it falls out of the kind 
    -- of things I was looking at, but I don't get it)

    turnedLeft :: Vertex -> Vertex -> Vertex -> Bool
    turnedLeft (x1,y1) (x2,y2) (x,y)
        = let (s,t) = (x - x1, y - y1)
              (u,v) = (x - x2, y - y2)
          in s * v >= t * u

Exercies 2.5  Another way to calculate polygon area

This exercise comes in 3 parts:

• new algorithm for calculating area
  
  
• why is it more efficient?
  
  
• what do we do with self-crossing polygons?
  
  

Once I sat down with a cup of tea to look at this clearly, it seemed
quite straightforward.  Obviously I managed to make it nonterminating
by trying to be clever with the base case.  I was trying to deal with
the base that we bring the first vertex back again.  In the end, I've
just appended (++ [v1]) though we haven't yet learnt the (++) operator
here, I wonder how you would do this using just what we've learnt so
far?

 -- this is the area function for exercise 2.5
 area2 :: Shape -> Float

 area2 (Polygon (v1 : vs)) = polyArea2 (v1 : vs ++ [v1] )
     where polyArea2  :: [Vertex] -> Float
           polyArea2 (v2 : v3 : vs') = trapArea v2 v3
             + polyArea2 (v3 : vs')
           polyArea2 _ = 0

 -- make area2 work for the other shapes
 area2 s = area s

Of course we need the area for a trapezoid.  Remember these aren't
arbitrary trapezoids, they're against the X axis, so they're basically a
rectangle with a right-angled triangle sitting on them.

And whaddaya know, we have functions to calculate these areas!

  trapArea :: Vertex -> Vertex -> Float
  trapArea (x1,y1) (x2,y2) =
      let baseWidth = x2 - x1
          baseHeight = min y1 y2
          triHeight  = max y1 y2 - baseHeight
      in    (area (Rectangle baseWidth baseHeight)) 
          + (area (RtTriangle baseWidth triHeight))

Now, remember that if X increases from x1 to x2, we add, but if it
decreases, we subtract.  We haven't seen conditional statements yet, but
handily if baseWidth is negative, the result of area Rectangle or area
RtTriangle will be negative also!

(This is an implementation detail really, the area function might throw
an error instead, or correct to positive.  So we might choose to inline
like so instead:

   in (baseWidth * baseHeight) + (0.5 * (baseWidth * triHeight))

Now, this seems to give sensible results for