UPenn CIS 194 Homework 4: Higher-order programming
hlint

hlint is a great tool for improving your mastery of Haskell idioms and syntax.

For example, here is one thing (of several) it found in your code:

input.hs:20:40: Warning: Avoid lambda
Found:
  \ x -&gt; x &gt; 1
Why not:
  (&gt; 1)


I would study the output of hlint.

fun1'

Looks fine.

fun2'

Stylistically I like to avoid long inline expressions. Use let and where to define meaningful subexpressions. I find this more readable (also
combining the hlint suggestion):

fun2' = sum . filter even . takeWhile (&gt; 1) . iterate collatz
  where collatz x = if (even x) then div x 2 else 3 * x + 1


collatz could even be a top-level function because it is generally useful.

makeTree

You are repeating the expressions makeTree a l and makeTree a r.
GHC might be able to detect the common sub-expression and unify the two
so that they are only evaluated once.

ghci doesn't do any CSE, so the same call will be executed twice.

In most cases it's best to use a where or let to ensure the expression
is only evaluated once:

| height l &lt;= height r =
    let left = makeTree a l
    in  Node (height left + 1) left m r         


More info on GHC and CSE: https://wiki.haskell.org/GHC/FAQ#Does_GHC_do_common_subexpression_elimination.3F

Also, height looks like it would be generally useful - why not expose it at the top level?

xor

Looks like it will work, but since you are not specifying a type for s
it will likely default to being an Integer.

But you don't need a whole Integer to keep track of the parity of a number. In fact, you can get by with simply a Bool.

As a extension to this exercise, try to write xor without using addition.

myFoldl

Try to write it without using reverse.

Hint: You have to build up a higher-order function.

Your answer will look like:

foldl f a xs =  (some big function) a


where (some big function) will be a foldr (\g x -&gt; ...) g0 xs.

Another hint: With a fold like:

foldr h y xs


you know that y = foldr h y [], so use this to determine what g0 is.

Sundram

Stylistically I would use list comprehensions as much as possible - replacing map and filter.

Instead of:

sieveSundaram n = map (\x -&gt; 2 * x + 1) (genSieve n)


I would write:

sieveSundaram n = [ 2*x+1 | x &lt;- genSieve n]


and instead of:

genCrossed m = map (\(i, j) -&gt; (i + j + 2 * i * j)) (filter valid (cartProd [1..m] [1..m]))


I would write:

genCrossed m = [ i+j+2*i*j | (i,j) &lt;- cartProd [1..m] [1..m], valid (i,j) ]


Also, you are computing the expression i + j + 2 * i * j twice. Can you think of a way of organizing your code so that it is only computed once?

valid

The where clause in the valid function can be dropped if you define it this way:

valid (i,j) = ...


Given a value for m, how many pairs is valid examining? Can you think of a way to reduce that number by about half?