haskell

Haskell99 from a JS background Pt.1

an.tran

— 5 min read

In an attempt to bend my brain and learn Functional Programming, I started with Haskell. This is an ongoing document of me trying to solve the H99: Ninety-nine Haskell Problem. Every challenge here has solutions provided by the community, and I'll try and reason those code using syntax of JavaScript. You can actually see my progress throughout this series, where I struggle to understand even the simplest function composition in the first few questions.

This is Pt.1: From H1 to H10.

H1: MyLast

Simplest implementation, off the top of my mind

myLast :: [a] -> a
myLast [] = error "No last element of empty list"
myLast [element] = element
myLast (_ : remaining) = myLast remaining

This is quite uninteresting and verbal, which is how a person who has just known pattern matching would do

Another interesting 1-liner in the solution is:

myLast2 :: [a] -> a
myLast2 = foldr1 (const id)

This implementation make use from the very quirky function const id. What it does is returning the second parameter of the two parameters passed in. const and id are both included in Prelude (stdlib).

-- Prelude implementation
const x y = x
id a = a

-- The const_id function
const_id :: a -> b -> b
const_id = const id

const_id 1 2 
-- should return 2

What the heck, you may wonder. Let me translate that to JS. Remember that for multiple parameters function in Haskell, it must be written as a fully curried form in JS.

let const_func = (x) => ((y) => x); // bracket added for clarity
let id_func = (a) => a;

let const_id_func = const_func(id_func)
//          == ( (x) => ((y) => x  ) (  (a) => a  ) 
//          the whole bunch (a) => a replace x
//          ==           (y) => ((a) => a)

const_id_func (1) (2)
//          == (    (  (y) => ((a) => a) ) (1)   ) (2)
//          ==      (     (a) => a       )  (2)
//          ==    2

That's a handful of bracket. But it is clear now, that calling this const_id function will return 2

Okay back to the foldr1 function. It take a function and a list, then call that function on the second last element and the last element of the list. Then it call the function on the third last element and the previous result, so on up to the first. So Array.prototype.reduceRight on JS. foldr1 is a version of foldr, but foldr has an initial value

foldr1 f [1,2,3,4] = f (1, f(2, f(3, 4)))
// note

Combine that

myLast2 = foldr1 (const_id)

myLast2 [1,2,3,4]
-- = const_id(1, const_id(2, const_id(3, 4) ) )
-- = const_id(1, const_id(2, 4) )
-- = const_id(1, 4)
-- = 4

Phew. Also there is another substitute for const id is: flip const

-- Prelude implementation of flip
flip f x y = f y x

-- Another myLast
myLast3 = foldr (flip const)

H2: MyButLast

My solution:

myLast :: [a] -> a
myLast [] = error "No last element of empty list"
myLast [element] = element
myLast (_ : remaining) = myLast remaining

main :: IO ()
main = do

  print (myLast2 [1, 2, 3, 4])
  print (myLast2 "hello")

  print (const id 1 2)
  print (const 1 2)

For this particular problem, there is no very cool solution. They mostly make use of multiple Prelude function

myButLast'''''' = head . reverse . init
myButLast'''' = head . tail . reverse

There is a new operator . This just mean: apply the parameter from the rightmost function to the left

head . tail . reverse [1,2,3]
-- = head . tail [3,2,1]
-- = head . [2,1]
-- = 2

head . reverse . init [1,2,3]
-- = head . reverse [1, 2]
-- = head [2, 1]
-- = 2

H3: ElementAt

We need to make a function that access an index on an array, but count from 1

elementAt [1,2,3,4,5] 3 == 3

This is a cakewalk using the infix !! operator.

elementAt :: [a] -> Int -> a
elementAt list index = list !! (index + 1)

But let's challenge ourselves with other solutions. First, a pattern matching one

elementAt' :: [a] -> Int -> a
elementAt' [] _ = error "index out of bound"
elementAt' list x
  | x < 1 = error "index out of bound"
  | x == 1 = element
  | x > 0 = elementAt' remainder (x - 1)
  where
    (element : remainder) = list

Second, a point free version:

elementAtPointFree :: Int -> [a] -> a
elementAtPointFree = (last .) . take . (+ 1)

But what the heck is point free? When I first read the word "point-free" I was confused, because there is a lot of point . in the code. The actual meaning of "point-free", like many other Haskell keywords, comes from math. Point free function mean we don't specify the parameters of the function when we write it, rather construct the function by combining other functions. In this section above, we make use of the function composition operator .. This operator is taken directly from Math function composition, (f . g) x = f (g(x)). We read function composition chain by applying the value on each function from leftward

Let's start filling in "points"

elementAtPointFree index = (last .) . take . (+1) index
  • The index will be applied to (+1) first, which is the index in base 1.
  • Then this index is given to take , which will returns a function that is waiting for an array and will return an array.
  • Then this function is given to last . . This will return last . theFunctionWaitingForAnArray
  • Now, if I pass an array to last . theFunctionWaitingForAnArray, it will call theFunctionWaitingForAnArray on the array, then pass that resulting array to last to get an element

Note that this implementation doesn't follow the parameter order we want. So we can just flip it first

elementAtPointFree' :: [a] -> Int -> a
elementAtPointFree' = flip ((last .) . take . (+ 1))

-- or, we can use the fancy $
elementAtPointFree' = flip $ (last .) . take . (+1)

The $ operator is the "function applicator", but it has the lowest precedence. Essentially the Haskell parser will skip over the $, evaluate all the operator on the right hand side and apply it to the function on the left.

H4: Get Length of List

Official solutions: http://wiki.haskell.org/99_questions/Solutions/4

In usual fashion, an implementation with pattern matching

myLength :: [a] -> Int
myLength [] = 0
myLength (x : xs) = myLength xs + 1

Some more with folding:

myLength2 :: [a] -> Int
myLength2 = foldl (\x _ -> x + 1) 0

myLength3 :: [a] -> Int
myLength3 = foldl (const . (+ 1)) 0

myLength4 :: [a] -> Int
myLength4 = foldr ((+) . const 1) 0
-- const 1 = x where x a = 1
-- (((+) . (const 1)) a) b = ((+) (x a)) b = (+ 1) b = b + 1

Another fun solution using zipping with an infinite list (also point free)

myLength5 :: [a] -> Int
myLength5 = fst . last . zip [1 ..]

H5: Reverse a List

Official solutions: http://wiki.haskell.org/99_questions/Solutions/5

Pattern matching:

myReverse :: [a] -> [a]
myReverse [] = []
myReverse (x : xs) = myReverse xs ++ [x]

Folding (this is actually how Prelude implement the reverse function): 

myReverse2 :: [a] -> [a]
myReverse2 = foldl (flip (:)) []

Note that the official solutions state that the pattern matching version we just had above is really inefficient (checkout a very detailed explanation here). We know that because Haskell maintains lists as lazy, front accessed linked list, appending (++) to the end of a long list (myReverse xs) means the code will have to traverse the longer first list and start appending stuffs to the end. This amount to an $O(n^2)$ complexity. We can do one better by constructing the list throughout the recursive run.

myReverseAccumulated :: [a] -> [a] -> [a]
myReverseAccumulated [] acc = acc
myReverseAccumulated (x : xs) acc = myReverseAccumulated xs (x : acc)

myReverse3 a = myReverseAccumulated a []

H6: Check list is Palindrome

Official solutions: http://wiki.haskell.org/99_questions/Solutions/6

Low skill level solution:

isPalindrome :: (Eq a) => [a] -> Bool
isPalindrome x = reverse x == x

Pattern matching:

isPalindrome2 :: (Eq a) => [a] -> Bool
isPalindrome2 [] = True
isPalindrome2 [_] = True
isPalindrome2 x = head x == last x && isPalindrome2 (init (tail x))

Read more