CSE230 handin 2

hw2.lhs

---
title: Homework #2, Due Sunday 2/5/13
---
 
This week's homework is presented as a literate Haskell file,
just like the lectures. This means that every line beginning with
`>` is interpreted as Haskell code by the compiler, while every other
line is ignored. (Think of this as the comments and code being reversed
from what they usually are.)
You can load this file into `ghci` and compile it with `ghc`
just like any other Haskell file, so long as you remember to save
it with a `.lhs` suffix.
 
To complete this homework, download [this file as plain text](hw2.lhs) and
answer each question, filling in code where
noted (some questions ask for explanations in addition to or instead
of code).
Your code must typecheck against the given type signatures.
Feel free to add your own tests to this file to exercise the functions
you write.  Submit your homework by sending this file, filled in
appropriately, to `[email protected]` with the subject "HW2"; you
will receive a confirmation email after submitting.  Please note that
this address is unmonitored; if you have any questions about the
assignment, email Pat at `[email protected]`.
 
This homework requires the graphics libraries from
The Haskell School of Expression:
 
> import Animation hiding (planets, translate)
> import Picture
> import Control.Applicative
> import Region
 
Part 0: All About You
---------------------
 
Tell us your name, email and student ID, by replacing the respective
strings below
 
> myName  = "Jesper Nielsen"
> myEmail = "[email protected]"
> mySID   = "u06143493"
 
 
 
Part 1: All About `foldl`
-------------------------
 
Define the following functions by filling in the "error" portion:
 
1. Describe `foldl` and give an implementation:
	Takes the element in the list from the left instead of from the right (foldr).
	Lets say used on a list [x,y,z] the fold would be: (f (f (f b x) y) z)
 
> myFoldl :: (a -> b -> a) -> a -> [b] -> a
> myFoldl f b [] = b
> myFoldl f b (x:xs) = (myFoldl f (f b x) xs)
 
2. Using the standard `foldl` (not `myFoldl`), define the list reverse function:
 
> myReverse :: [a] -> [a]
> myReverse = foldl (\a x -> x : a) []
 
3. Define `foldr` in terms of `foldl`:
 
> myFoldr :: (a -> b -> b) -> b -> [a] -> b
> myFoldr f b as = foldl (\b a -> f a b) b (myReverse as)
 
4. Define `foldl` in terms of the standard `foldr` (not `myFoldr`):
 
> myFoldl2 :: (a -> b -> a) -> a -> [b] -> a
> myFoldl2 f a bs = foldr (\b a -> f a b) a (myReverse bs)
 
5. Try applying `foldl` to a gigantic list. Why is it so slow?
	It is because haskell uses lazy evaluation.
	When it uses foldl on a List the unfolding would be like this (foldl f a [x1,x2,x3,x4]):
		(f (f (f (f a x1) x2) x3) x4)
	And first when the list is completely unfolded it would begin evaluate each of the functions starting from outside going in.
  (f ... (f (f x0 a) x1) ... ) 
   Try using `foldl'` (from [Data.List](http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data-List.html#3))
   instead; can you explain why it's faster?
   	They force the evaluation of each function to happen when the element is unfolded and thereby removes the lazyness.
 
Part 2: Binary Search Trees
---------------------------
 
Suppose we have the following type of binary search trees:
 
> data BST k v = Emp 
>              | Bind k v (BST k v) (BST k v) 
>              deriving (Show)
 
Define a `delete` function for BSTs of this type:
 
Helper function given two trees it takes the last and puts it in the right most branch of the first tree
 
> putRight :: BST k v -> BST k v -> BST k v
> putRight Emp r = r
> putRight (Bind k v t1 t2) r = (Bind k v t1 (putRight t2 r)) 
 
> delete :: (Ord k) => k -> BST k v -> BST k v
> delete k Emp = Emp
> delete k (Bind k' v t1 t2) = 
>	if k < k'
>	then	Bind k' v (delete k t1) t2
>	else if k == k'
> 	then	putRight t1 t2
> 	else	Bind k' v t1 (delete k t2)
 
Part 3: Animation
-----------------
 
This part of the homework constructs an animation of a model
solar system.
We begin by defining various helpful functions:
 
> translate :: (Float, Float) -> Picture -> Picture
> translate v p =
>     case p of
>       Region c r -> Region c (Translate v r)
>       p1 `Over` p2 -> (translate v p1) `Over` (translate v p2)
>       EmptyPic -> EmptyPic
 
> -- Translate a picture behavior by a given vector behavior
> translateB :: (Behavior Float, Behavior Float) -> Behavior Picture -> Behavior Picture
> translateB (x,y) p = lift2 translate (zipB (x,y)) p
 
> -- Convert a pair of behaviors into a pair behavior
> zipB :: (Behavior a, Behavior b) -> Behavior (a,b)
> zipB (Beh b1, Beh b2) = Beh (\t -> (b1 t, b2 t))
 
> -- Construct a circle behavior
> circ :: Behavior Float -> Behavior Shape
> circ r = ell r r
 
> sun :: Behavior Picture
> sun = reg (lift0 Yellow) (shape (circ 1))
 
> mercury :: Behavior Picture
> mercury = reg (lift0 Red) (shape (circ 0.1))

> earth :: Behavior Picture
> earth = reg (lift0 Blue) (shape (circ 0.2))

> moon :: Behavior Picture
> moon = reg (lift0 Cyan) (shape (circ 0.1))
 
The following define the main action of the solar system simulator.
You'll want to replace the right-hand side of `planets` with your
solar system.
 
> planets :: Behavior Picture
> planets = orbit (orbit moon earth 5 1 0.1) (orbit mercury sun 2 2 0.2) 1 4 0.4
 
> main :: IO()
> main = 
>   do animateB "Solar system" planets
 
Before starting the exercise proper, let's make our lives easier. By
making the Behavior type a member of the Applicative typeclass, we'll
give ourselves a way to avoid a lot of tedious "liftn" operations in
our code.
This may require providing additional definitions not explicitly
mentioned here. You should verify that your definition of the
applicative instance has the required properties (but don't need to
turn in a proof).
If you don't understand the above, some good references are
Chapter 18 of The Haskell School of Expression
and the
[section on applicative functors](http://en.wikibooks.org/wiki/Haskell/Applicative_Functors)
in the Haskell wikibook.


> instance Functor Behavior where
> 	fmap f (Beh a) = Beh (f . a)
 
> instance Applicative Behavior where
> 	pure x                 	= Beh (\t -> x)
>	(<*>) (Beh ab) (Beh a)	= Beh (\t -> ((ab t) (a t))) 


Next, use the provided function translateB to write a function
 
> orbit :: Behavior Picture -- the satellite
>       -> Behavior Picture -- the fixed body
>       -> Float            -- the frequency of the orbit
>       -> Float            -- the x-radius of the orbit
>       -> Float            -- the y-radius of the orbit
>       -> Behavior Picture
> orbit sat body freq x y = let satMov = translateB (Beh (\t -> x*cos(t*freq)), Beh (\t -> (y*sin(t*freq)))) sat in
>								 let satScale = scaleBehPic (Beh (\t -> 1 - sin(t*freq)/2)) satMov in
>									cond (Beh (\t -> y*sin(t*freq) < 0)) 
>										(satScale `over` body) 
>										(body `over` satScale)	


> scalePic :: Float -> Picture -> Picture
> scalePic v (Region c r) = Region c (Scale (v,v) r)
> scalePic v (p1 `Over` p2) = (scalePic v p1) `Over` (scalePic v p2)
> scalePic v EmptyPic = EmptyPic

> scaleBehPic :: Behavior Float -> Behavior Picture -> Behavior Picture
> scaleBehPic scale b = (fmap scalePic scale) <*> b
 
that takes two picture behaviors and makes the first orbit around the
second at the specified distance and with the specified radii. That
is, the two pictures will be overlayed (using `over`) and, at each time
$t$, the position of the satellite will be translated by
$xradius * cos(t * frequency)$ in the $x$ dimension and by
$yradius * sin(t * frequency)$ in the $y$ dimension.
 
Test your function by creating another circle, `mercury`, colored red
and with radius `0.1`, and making it orbit around the sun with a
frequency of `2.0`, and with radii of `2.0` and `0.2` in the x and y axes,
respectively.
 
A problem you might have noticed is the overlay behavior of
planets. For this part modify orbit to put planets over or under each
other. Hint: you might find the lifted conditional `cond` from SOE
useful for this part.
 
Modify your functions (and write any support functions that you find
necessary) to make the orbital distances and planet sizes shrink and
grow by some factor (you can pass this factor as parameter to the
orbit function), according to how far the planets are from the
observer. For example, the earth and moon should look a little smaller
when they are going behind the sun, and the orbital distance of the
moon from the earth should be less.
 
Choose the scaling factor so that the solar system simulation looks
good to you.
 
*Optional:* Add some other planets, perhaps with their own moons. If
you like, feel free to adjust the parameters we gave above to suit
your own aesthetic or astronomical tastes. Make sure, though, that the
features requested in previous parts --- growing, shrinking,
occlusion, etc. --- remain clearly visible.
 
Credits
-------
 
Part 3 is taken from 
<a href="http://www.cis.upenn.edu/~bcpierce/courses/552-2008/">
UPenn's CIS 522
</a>.