Dictionaries and arrays

Full source

Problem 1

fromList : List (comparable, v) -> Dict comparable v
fromList list = 
  let
    step (k, v) acc =
      Dict.insert k v acc
  in
    List.foldl step Dict.empty list

Problem 2

Here's a wordy version:

reverse : Dict comparableKey comparableVal
       -> Dict comparableVal comparableKey
reverse dict = 
  let
    step k v acc =
      Dict.insert v k acc
  in
    Dict.foldl step Dict.empty dict

We could make it more terse.

Given that the important thing here is flipping parameters, we could use flip Dict.insert to rearrange the order of k and v:

reverse dict = 
  let
    step k v acc =
      (flip Dict.insert) k v acc      -----------------
  in
    Dict.foldl step Dict.empty dict

Now we can drop all the step parameters (partial application):

reverse dict = 
  let
    step =
      (flip Dict.insert)
  in
    Dict.foldl step Dict.empty dict

But it seems silly now to have a step at all, so let's inline it:

reverse dict = 
  Dict.foldl (flip Dict.insert) Dict.empty dict

The dict parameter seems to add little, so we can drop it:

reverse2 = 
  Dict.foldl (flip Dict.insert) Dict.empty

Problem 3

Because of the requirement for sort order, the list should be reversed after being created. For fun, I'm using foldl to reverse it.

toList : Dict comparable val -> List (comparable, val)
toList dict =
  let
    step k v acc =
      (k, v) :: acc
  in
    dict
      |> Dict.foldl step []
      |> List.foldl (::) [] -- or `List.reverse`

Problem 4

uncurry : (a1 -> a2 -> r) -> (a1, a2) -> r
uncurry fnTaking2Args (arg1, arg2) =
  fnTaking2Args arg1 arg2

---

A rewritten exercise 1 solution starts with this implementation of step:

    step (k, v) acc =
      Dict.insert k v acc

Using partial application, acc can be dropped:

    step (k, v) =
      Dict.insert k v

step now looks a lot like the definition of uncurry, except at the Dict.insert is a constant instead of being passed in. So let's pass in Dict.insert:

fromList list = 
  let
    step f (k, v) =
      f k v
  in
    List.foldl (step Dict.insert) Dict.empty list

But now step is exactly uncurry, so we can use it instead:

fromList list = 
  List.foldl (uncurry Dict.insert) Dict.empty list

And, while we're at it, we can drop the list argument (partial application again):

fromList = 
  List.foldl (uncurry Dict.insert) Dict.empty

---

curry : ( (a1, a2) -> r) -> a1 -> a2 -> r
curry fnTakingTuple arg1 arg2 =
  fnTakingTuple (arg1, arg2)

Problem 5

map : (comparable -> a -> b) -> Dict comparable a -> Dict comparable b
map f dict =
  let
    step (key, value) acc =
      Dict.insert key (f key value) acc
  in
    dict
      |> Dict.toList
      |> List.foldl step Dict.empty

Here's something interesting: you can use map to change the type of the value from, say, an Int to a String:

> input = Dict.singleton 1.0 333
Dict.fromList [(1,333)] : Dict Float number
> Dict.map (\_ val -> toString val) input
Dict.fromList [(1,"333")] : Dict Float String

You cannot, however, change the type of the keys. (Do you see what in the type signature prevents that?) I don't know the reason for the restriction.

(What prevents it: The Dict argument and result use different type variables for the original and result value (a and b). They use the same variable (comparable) for both key values, meaning the original and result Dicts must share the key type.)

Problem 6

withValue : (value -> result) -> (key -> value -> result)
withValue f key = f 

This is interesting, in that it's a specific example of a perhaps-more-general situation: adapt a function that takes one argument into one that takes two arguments, the first of which is ignored.

In FP jargon, this process of adapting functions to work in a more complicated context is often referred to as "lifting".