Ch 05 Daily 2

Stone age functions: write using a minimum of Haskell tools. Concentrate on writing well-crafted functions.

Good to use

• Pattern matching. Example: (x:xs).

• Recursion.

• “Multiple definitions.” Example:

    f 0 = 0
    f 1 = 1
    f n = f (n-1) + f (n-2)
  

• Basic functions like arithmetic, : and ++.

Avoid

• Conditionals (guards) and if statements. Use “multiple definitions” whenever possible.
• Using head and tail. Choose pattern matching instead.
• Counting the items in a list (length and similar constructions). Look for another way to achive what you want, maybe with a recursive function.

Group I

You can just use a type of Int if you prefer not to think about the generic type parameter a.

• mylength :: [a] -> Int
• mylast :: [a] -> a
• mynull :: [a] -> Bool. Should be be fast for an input [1..1000*1000*1000].
• mysum :: [Int] -> Int
• myzip :: [a] -> [b] -> [(a,b)]

Group II

You can use a type of Int instead of a if you prefer.

• myreplicate :: Int -> a -> [a]
• myminimum :: [a] -> a Requires either min or using guards.
• mytake :: Int -> [a] -> [a]
• myreverse :: [a] -> [a]

Group IV: Combinations

there is one function to write: produce all of the k element combinations of the elements in a given list. This function can be challenging. We intend to work through creating an example editing the code.

• Write a function allComb :: Int -> [a] -> [[a]] to create a list of all “combinations” of a given number of elements of the list. Combinations means the order you write the elements in does not matter, so you should only give one of [1,2] or [2,1].

Notes:

• Write examples and look for patterns.
• Using reverse is misleading; it really only appears for 2 elements. Starting with 3 elements the pattern is more complex.
• If factorial appears in your answer, look for a simpler, more direct approach.
• Ignore the possibility that some of the elements are the same (“not distinct”).

Examples

Taking combinations of two items out of a list [1,2,3] should produce [[1,2],[1,3],[2,3]].

_3C2 = allComb 2 [1,2,3]
checks3 = [
  _3C2 == [[1,2],[1,3],[2,3]],
  length _3C2 == 3,
  ]

Taking three objects out of the list [1,2,3,4,5] should produce:

123 124 125 134 135 145
234 235 245
345

This:

_5C3 = allComb 5 [1..5]
checks5 = [
  _3C2 == [[1,2],[1,3],[2,3]],
  length _3C2 == 3,
  _5C3 ==
    [[1,2,3],[1,2,4],[1,2,5],[1,3,4],[1,3,5],[1,4,5],
     [2,3,4],[2,3,5],[2,4,5],
     [3,4,5]],
  length _5C3 == 10
  ]

Choosing 5 items from a list of 10 should give 252 items.

checks10 = [length (allComb 5 [1..10]) == 252]