0410 (Friday, Week 1)

Nested Patterns

negate : List Bool -> List Bool
negate xs =
  case xs of
    [] ->
      []
    x :: tail ->                -- x is a variable pattern
      not x :: negate tail

The variable pattern x here matches any Bool. Instead, could choose to pattern match on Bool data constructors, as follows. The second and third branches are nested patterns, because a (non-variable) Bool pattern appears within the (non-variable) List pattern.

negate : List Bool -> List Bool
negate xs =
  case xs of
    [] ->
      []
    True :: tail ->
      False :: negate tail
    False :: tail ->
      True :: negate tail

Both True and False cases are handled in the same way (i.e. not x :: negate tail), so arguably the first version, with the variable pattern, is preferable. But this is really a stylistic choice.

Short-Circuiting

How about the variable and nested pattern style for the following function?

all : List Bool -> Bool
all xs =
  case xs of
    []        -> True
    x :: tail -> x && all tail

all : List Bool -> Bool
all xs =
  case xs of
    []            -> True
    False :: tail -> False
    True :: tail  -> all tail

Maybe the latter version performs better, because the former evaluates all tail even when x is False? No, they're both the same, because Elm short-circuits the evaluation of the second argument to (&&) if the first evaluates to False. You may enjoy doing some investigative journalism to test this out for yourself (Hint: Debug.log). If you do, also try ((&&) x (all tail)).

Mutually Recursive Functions

All definitions at the top-level are mutually recursive. Notice how isOdd refers to isEven even though it appears later in the file.

isOdd : Int -> Bool
isOdd n =
  if n == 0 then
    False
  else
    isEven (n-1)

isEven : Int -> Bool
isEven n =
  if n == 0 then
    True
  else
    isOdd (n-1)

Similar thing, but where the mutually recursive functions are defined within a let:

odd : Int -> Bool
odd =
  let
    isOdd : Int -> Bool
    isOdd n =
      if n == 0 then
        False
      else
        isEven (n-1)
{-
  in
  let       
-}
    isEven : Int -> Bool
    isEven n =
      if n == 0 then
        True
      else
        isOdd (n-1)
  in
    isOdd

However, if we split the above into two separate let-expressions (by removing the comment), we get a variable-not-found error.

In general, the structure of a let-expression is

let
  x1 = e1
  x2 = e2
    ...
  xn = en
in
  body

where n >= 1. The variables x1 through xn are in scope for each of the definitions e1 and en, hence, the equations are mutually recursive. (And, of course, the variables are in scope in the body expression.)

map : (a -> b) -> List a -> List b
map f xs =
  case xs of
    [] ->
      []
    x :: tail ->
      f x :: map f tail

stutter : List a -> List a
stutter xs =
  case xs of
    [] ->
      []
    x :: tail ->
      x :: x :: stutter tail

[scroll down to see answers]

[didn't get to this in class]

[scroll down to see answers]

Answers

1

Here's the recursive case for List.map and for the direct-recursion versions of the four functions we are considering:

--   f x        :: map f tail       -- List.map
--
--   not x      :: negate tail
--   2 * x      :: double tail
--   (\_ -> ()) :: nullify tail
--   x :: x     :: stutter tail     -- doesn't fit the pattern
--   ^^^^^^

The expression x :: x in the corresponding position does not make sense on its own:

> bad x = x :: x
-- INFINITE TYPE ----------------------------------------------------------- elm

I am inferring a weird self-referential type for x:

3| bad x = x :: x
       ^
Here is my best effort at writing down the type. You will see ∞ for parts of the
type that repeat something already printed out infinitely.

    List ∞

Staring at this type is usually not so helpful, so I recommend reading the hints
at <https://elm-lang.org/0.19.0/infinite-type> to get unstuck!

We have something more along the lines of x :: x :: [] — that is, [x, x] — but this can't be cons-ed on to the result of the recursive call. Instead:

mapMany : (a -> List b) -> List a -> List b
mapMany f xs =
  case xs of
    [] ->
      []
    x :: tail ->
      f x ++ mapMany f tail

stutter xs = mapMany (\x -> [x,x])                   xs 
negate  xs = mapMany (List.singleton << not)         xs
double  xs = mapMany (List.singleton << ((*) 2))     xs
nullify xs = mapMany (List.singleton << (always ())) xs

Alternate definition of mapMany, in two steps:

concat : List (List a) -> List a
concat xss =
  case xss of
    [] ->
      []
    xs :: tail ->
      xs ++ concat tail

mapMany : (a -> List b) -> List a -> List b
mapMany f xs =
  concat (map f xs)

"mapMany" is known as List.concatMap. You might hear concat sometimes referred to as "flatten".

2

Left:

foldl : (a -> b -> b) -> b -> List a -> b
foldl f acc xs =
  case xs of
    [] ->
      acc
    x :: tail ->
      let newAcc = f x acc in
      foldl newAcc tail

An illustrative unfolding (pun intended) of evaluation, though not one that corresponds exactly to Elm, or OCaml, or Haskell, or Racket...

    foldl (::) [] [1,2,3]
==>
    let newAcc1 = (::) 1 [] in
    foldl (::) newAcc1 [2,3]
==>
    let newAcc1 = (::) 1 [] in
    let newAcc2 = (::) 2 newAcc1 in
    foldl (::) newAcc2 [3]
==>
    let newAcc1 = (::) 1 [] in
    let newAcc2 = (::) 2 newAcc1 in
    let newAcc3 = (::) 3 newAcc2 in
    foldl (::) newAcc3 []
==>
    let newAcc1 = (::) 1 [] in
    let newAcc2 = (::) 2 newAcc1 in
    let newAcc3 = (::) 3 newAcc2 in
    newAcc3
==>
    [3, 2, 1]

Right:

foldr : (a -> b -> b) -> b -> List a -> b
foldr f init xs =
  case xs of
    [] ->
      init
    x :: tail ->
      let result =
        foldr f init tail
      in
      f x result

An illustrative unfolding:

    foldr (::) [] [1,2,3]
==>
    let result1 =
      foldr (::) [] [2,3]
    in
    (::) 1 result1
==>
    let result1 =
      let result2 =
        foldr (::) [] [3]
      in
      (::) 2 result2
    in
    (::) 1 result1
==>
    let result1 =
      let result2 =
        let result3 =
          foldr (::) [] []
        in
        (::) 3 result3
      in
      (::) 2 result2
    in
    (::) 1 result1
==>
    let result1 =
      let result2 =
        let result3 =
          []
        in
        (::) 3 result3
      in
      (::) 2 result2
    in
    (::) 1 result1
==>
    [1, 2, 3]