08.08.07

Exercise 9.7

Posted in Uncategorized at 11:13 pm by admin

twice :: (a -> a) -> a -> a
twice f = (\x -> f (f x))

twice twice applies the function 4 times:

twice twice f
= twice (\y -> f (f y))
= (\x -> (\y -> f (f y)) ((\y -> f (f y)) x))
= (\x -> (\y -> f (f y)) (f (f x)))
= (\x -> f (f (f (f x))))

twice twice twice and twice (twice twice) each apply the function 16 times.

Exercise 9.6

Posted in Uncategorized at 10:52 pm by admin

appendr = foldr (flip (++)) []
appendr [x,y,z]
= foldr (flip (++)) [] [x,y,z]
= flip (++) x (flip (++) y (flip (++) z []))
= flip (++) x (flip (++) y ([] ++ z))
= flip (++) x (([] ++ z) ++ y)
= (([] ++ z) ++ y) ++ x

Running time of appendr is O(n2) since (++) traverses the length of its first argument.

appendl = foldl (flip (++)) []
appendl [x,y,z]
= foldl (flip (++)) [] [x,y,z]
= flip (++) (flip (++) (flip (++) [] x) y) z
= flip (++) (flip (++) (x ++ []) y) z
= flip (++) (y ++ (x ++ [])) z
= z ++ (y ++ (x ++ []))

Running time of appendl is O(n).

(Technical error 16 applies to this exercise.)

Exercise 9.5

Posted in Uncategorized at 10:35 pm by admin

applyAll :: [(a -> a)] -> a -> a
applyAll [] x = x
applyAll (f:fs) x = f (applyAll fs x)

Exercise 9.4

Posted in Uncategorized at 10:34 pm by admin

applyEach :: [(a -> b)] -> a -> [b]
applyEach [] _ = []
applyEach (f:fs) x = f x : applyEach fs x

Exercise 9.3

Posted in Uncategorized at 10:33 pm by admin

ys :: [Float -> Float]

Exercise 9.2

Posted in Uncategorized at 10:30 pm by admin

flip f x y = f y x
flip (flip f) x y 
= flip f y x 
= f x y
∴ flip (flip f) = f

Exercise 9.1

Posted in Uncategorized at 10:25 pm by admin

(Polygon pts) `containsS` p 
    = let leftOfList = map isLeftOfp
                       (zip pts (tail pts ++ [head pts]))
          isLeftOfp = isLeftOf p
      in and leftOfList

08.07.07

Exercise 8.13

Posted in Uncategorized at 11:25 pm by admin

First, the new definitions:

data Region = UnitCircle
            | Polygon [Coordinate]
            | AffineTransform Matrix3x3 Region
            | Empty
              deriving Show
 
type Vector3 = (Float, Float, Float)
type Matrix3x3 = (Vector3, Vector3, Vector3)
type Matrix2x2 = ((Float, Float), (Float, Float))

And some old ones that will suffice unchanged:

type Coordinate = (Float, Float)
type Ray = (Coordinate, Coordinate)
 
isLeftOf :: Coordinate -> Ray -> Bool
(px,py) `isLeftOf` ((ax,ay), (bx,by))
    = let (s,t) = (px-ax, py-ay)
          (u,v) = (px-bx, py-by)
      in s * v >= t * u
 
isRightOf :: Coordinate -> Ray -> Bool
(px,py) `isRightOf` ((ax,ay), (bx,by))
    = let (s,t) = (px-ax, py-ay)
          (u,v) = (px-bx, py-by)
      in s * v <= t * u
 
containsR :: Region -> Coordinate -> Bool
(Polygon pts) `containsR` p
    = let leftOfList = map isLeftOfp (zip pts (tail pts ++ [head pts]))
          isLeftOfp p' = isLeftOf p p'
          rightOfList = map isRightOfp (zip pts (tail pts ++ [head pts]))
          isRightOfp p' = isRightOf p p'
      in and leftOfList || and rightOfList
Empty `containsR` p = False

Now we have the new forms of containsR to write. The UnitCircle is easy:

UnitCircle `containsR` (x,y) = x^2 + y^2 <= 1

And in general, the transform of a region contains a point if the region contains the inverse transform of that point.

(AffineTransform m r) `containsR` (x,y)
    = if determinant3 m == 0
      then singularContains m (x,y)
      else let m' = inverse m
               (x', y', _) = matrixMul m' (x,y,1)
           in r `containsR` (x', y')

Now some standard code for multiplying and inverting matrices:

matrixMul :: Matrix3x3 -> Vector3 -> Vector3
matrixMul (r1, r2, r3) v
    = (dotProduct r1 v,
       dotProduct r2 v,
       dotProduct r3 v)
 
dotProduct :: Vector3 -> Vector3 -> Float
dotProduct (a,b,c) (x,y,z) = a*x + b*y + c*z
 
inverse :: Matrix3x3 -> Matrix3x3
inverse ((a,b,c), (d,e,f), (g,h,i))
    = let det = determinant3 ((a,b,c), (d,e,f), (g,h,i))
          a' = determinant2 ((e,f), (h,i)) / det
          b' = determinant2 ((c,b), (i,h)) / det
          c' = determinant2 ((b,c), (e,f)) / det
          d' = determinant2 ((f,d), (i,g)) / det
          e' = determinant2 ((a,c), (g,i)) / det
          f' = determinant2 ((c,a), (f,d)) / det
          g' = determinant2 ((d,e), (g,h)) / det
          h' = determinant2 ((b,a), (h,g)) / det
          i' = determinant2 ((a,b), (d,e)) / det
      in ((a',b',c'), (d',e',f'), (g',h',i'))
 
determinant3 :: Matrix3x3 -> Float
determinant3 ((a,b,c), (d,e,f), (g,h,i))
    = let aei = a * e * i
          afh = a * f * h
          bdi = b * d * i
          cdh = c * d * h
          bfg = b * f * g
          ceg = c * e * g
      in aei - afh - bdi + cdh + bfg - ceg
 
determinant2 :: Matrix2x2 -> Float
determinant2 ((a,b), (c,d))
    = a * d - b * c

The only thing left is the question of how to deal with a singular (non-invertible) matrix. If an affine matrix is non-invertible, that means that AE – BD = 0. Either all four coefficients are 0, or AE = BD. If all 4 are 0, then every point in the region will be collapsed into the single point (C,F), and we need to check that this is the given point. If AE = BD otherwise, we have for any point (x,y) in the region:

x' = Ax + By + C
y' = Dx + Ey + F
Dx' = ADx + BDy + CD
Ay' = ADx + AEy + AF
    = ADx + BDy + AF [AE = BD]
∴ Dx' - Ay' = CD - AF
Dx' - Ay' + AF - CD = 0

so any point in the region will be collapsed into the line Dx’ – Ay’ + AF – CD = 0, and we need to check that the given point satisfies this equation.

singularContains :: Matrix3x3 -> Coordinate -> Bool
singularContains ((a,b,c), (d,e,f), _) (x,y)
    = if (a == 0 && b == 0 && d == 0 && e == 0)
      then (x == c && y == f)
      else (d*x - a*y + a*f - c*d == 0)

08.05.07

Exercise 8.12

Posted in Uncategorized at 9:26 pm by admin

There are a couple of ways to do this (the basic problem being how to deal with concave polygons). One way is to convert the polygon to a convex hull and a list of triangles representing subtractions from the convex hull, then check containment within the hull and non-containment within the triangles. However, I present a simpler way: pick a point guaranteed not to be in the polygon, form the ray between that and the point in question, and count the number of times that ray crosses the polygon sides. If it’s even, the point is outside the polygon. This method also works for self-crossing polygons (provided that one considers any internal spaces formed as outside the polygon: consider a pentagram for example).

raysCross :: Ray -> Ray -> Bool
raysCross (a,b) (x,y) = let h = isLeftOf x (a,b) && isRightOf y (a,b)
                            i = isLeftOf y (a,b) && isRightOf x (a,b)
                            j = isLeftOf a (x,y) && isRightOf b (x,y)
                            k = isLeftOf b (x,y) && isRightOf a (x,y)
                        in (h || i) && (j || k)
 
countCrossings :: Ray -> [Ray] -> Int
countCrossings r rs = foldl (+) 0
                      (map (\x -> if raysCross r x then 1 else 0) rs)
 
guaranteedOutside :: [Vertex] -> Vertex
guaranteedOutside vs
    = (foldl maxop 0 xs + 1, foldl maxop 0 ys + 1)
    where (xs, ys) = unzip vs
          maxop a b = if a > b then a else b
 
containsS' :: Shape -> Coordinate -> Bool
(Polygon ps) `containsS'` p
    = let poutside = guaranteedOutside ps
      in (countCrossings (p,poutside)
          (zip ps (tail ps ++ [head ps]))) `mod` 2 == 1

See Exercise 8.4 for definitions of isLeftOf and isRightOf. I am also left feeling that there must be a more elegant way to count the number of list elements that fulfil a predicate (which is what countCrossings is really doing).

08.03.07

Exercise 8.11

Posted in Uncategorized at 10:37 pm by admin

See Exercises 2.4 and 5.1. Then:

area'' :: Shape -> Float
area'' (Polygon (v1:vs)) = if convex (Polygon (v1:vs))
                           then let areas = map ((v2, v3) -> triArea v1 v2 v3)
                                               (zip vs (tail vs))
                                in foldl (+) 0 areas
                           else error "Non-convex polygon"

« Previous Page« Previous entries « Previous Page · Next Page » Next entries »Next Page »