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 simple polygons, but let's
try with a concave one and check we get the right result.

  area2 $ Polygon [(0,0), (0,5), (5,10), (10,10), (5,5), (15,0)]

By my calculation this should give 75, and ghci does indeed give me
that result!

Though, so does area, which is odd.  Let's try a more complex concave
shape...

    area2 $ Polygon [(2,0),(2,4),(0,5),(2,6),(3,8),(4,6),(6,5),(4,4)]

This should give 14, and area2 does.  The old area function gives
27.999985.

Why is the new technique more efficient?

Because we take 2 vertices at a time and have to return to v1, the new
technique has more iterations v, rather than v-2, where v is the number
of vertices in the Polygon.  However the calculations involved are
trivial, multiplication and addition, with no square root, and no
additional call to distBetween.  I'd want to run a benchmark before
asserting definitely that area2 is more efficient, but it seems like a
good working assumption.

What is the correct notion of area for self-crossing polygons.

The naive view seems to be correct, that, for example, a bowtie
like Polygon [(0,0), (0,1), (2,0), (2,1)] is equivalent to 2
triangles, or Polygon [(0,0), (0,1), (1,0.5)] and
[(1,0.5), (2,0), (2,1)]

Sadly area2 returns a value of 0 for this case.  My first naive idea of
how to solve this problem would be detecting where the polygon
self-crosses and then rewriting it into separate polygons as above.

On the other hand, as with this bowtie case, if we suggest that area is
what is bounded to the right, say, of the perimeter, then as the
polygon self-crosses, the area to the other side is what is
being calculated.  Perhaps like a Möbius strip, the notion of area or
perimeter has actually changed in this geometry?

Wrapping up

That was a tough chapter, in my case, as much for the maths (trivial as
it might be to someone less flabby than me) as the Haskell.  I ended up
not completing Exercise 2.2 and I'd be especially interested to see a
basic solution to Exercise 2.4, but will probably come back to it later
on.