# Path to Beginnery in Functional Programming with Haskell - 1

## Path To Beginnery in Functional Programming with Haskell

See the first post in this series for an introduction to this series. Quick recap: I am trying to track my path completing Haskell programming projects from books I am reading. Feel free to message me on Twitter @chiroptical with any corrections or suggestions on new topics.

## Project 1

This is a short problem, but I was getting stuck on a `foldr`

implementation.
I wanted to write down the problem, reductions, correct solution, and some
alternate implementations to increase my understanding.

#### Definition of Problem

Implement `myMaximumBy`

using a fold. `myMaximumBy`

takes a comparison
function, of type `(a -> a -> Ordering)`

, and returns the greatest element of
the list based on the last value in the list which returned `GT`

. Some
examples:

```
Prelude> myMaximumBy (\_ _ -> GT) [1..10]
1
Prelude> myMaximumBy (\_ _ -> LT) [1..10]
10
Prelude> myMaximumBy compare [1..10]
10
```

#### Solving The Problem

The base case, or accumulator, is simply the first value in the list. My
initial thought is that given an empty list our function should return an
error. Side note: after additional thought I decided to implement a version which
returns `Maybe a`

, but I will show that in the **Practical Considerations**
section. If given a list with one element, simply return that element. Next we
need to define our folding function (for a `foldr`

),

```
folder :: (a -> a -> Ordering) -> a -> a -> a
folder f x acc = if f x acc == GT then x else acc
```

and the full `foldr`

with pattern matches for empty and single-item lists,

```
myMaximumBy :: (a -> a -> Ordering) -> [a] -> a
myMaximumBy _ [] = error "Cannot myMaximumBy on empty list!"
myMaximumBy _ [x] = x
myMaximumBy f xs = foldr (folder f) (head xs) $ tail xs
```

For a novice, this might look like working code as it will type check! However,
it doesn’t work correctly. A `foldr`

breaks down like this for `[a]`

with 3 items:

```
foldr g acc [a, a', a'']
-- ==
-- g a (g a' (g a'' acc))
```

Let’s take the example where,

```
-- Omitting types
g = folder f
f = \_ _ -> GT
-- Reduction (g x x' = x, always!)
-- 1. g a (g a' a'')
-- 2. g a a'
-- 3. a
```

Which is not what we are looking for! We actually want to return `a''`

. To
do that, we need `foldl`

,

```
folder :: (a -> a -> Ordering) -> a -> a -> a
folder f acc x = if f acc x == GT then acc else x
myMaximumBy :: (a -> a -> Ordering) -> [a] -> a
myMaximumBy _ [] = error "Cannot myMaximumBy on empty list!"
myMaximumBy _ [x] = x
myMaximumBy f xs = foldl (folder f) (head xs) $ tail xs
-- Reduction
-- 1. f (f a a') a''
-- 2. f a' a''
-- 3. a''
```

## Practical Considerations

#### Implement `... -> Maybe a`

Version

Let’s remove the version of `myMaximumBy`

which errors out by returning
`Nothing`

when given an empty list and a `Maybe a`

otherwise.

```
folder :: (a -> a -> Ordering) -> Maybe a -> a -> Maybe a
folder f (Just acc) x = if f acc x == GT then (Just acc) else (Just x)
folder _ _ _ = Nothing
myMaximumBy :: (a -> a -> Ordering) -> [a] -> Maybe a
myMaximumBy _ [] = Nothing
myMaximumBy _ [x] = Just x
myMaximumBy f xs = foldl (folder f) (Just $ head xs) $ tail xs
```

I don’t think `folder f _ x`

pattern in necessary, but it definitely doesn’t
hurt.

#### Implement `myMinimumBy`

For `myMinimumBy`

you simply replace `GT`

in `folder`

with `LT`

. With a little
abstraction, you can write both in a nice point-free style.

```
folder :: Ordering -> (a -> a -> Ordering) -> Maybe a -> a -> Maybe a
folder o f (Just acc) x = if f acc x == o then (Just acc) else (Just x)
folder _ _ _ _ = Nothing
myOrderingBy :: Ordering -> (a -> a -> Ordering) -> [a] -> Maybe a
myOrderingBy _ _ [] = Nothing
myOrderingBy _ _ [x] = Just x
myOrderingBy o f as = foldl (folder o f) (Just $ head as) $ tail as
myMaximumBy :: (a -> a -> Ordering) -> [a] -> Maybe a
myMaximumBy = myOrderingBy GT
myMinimumBy :: (a -> a -> Ordering) -> [a] -> Maybe a
myMinimumBy = myOrderingBy LT
```

## Wrapping Up

This wasn’t a particularly difficult problem or solution, but it was one of the
first cases where my code looked correct, type-checked, and failed. It is
really important to understand the difference between `foldr`

and `foldl`

. I am
starting to really enjoy point-free style in Haskell. When understood, it is
terse and beautiful.

Edits made on 10/18/18 cleaning up patterns with unneccesary named parameters.
Replace `(x:[])`

with `[x]`

.