The connection between the apply function and the s combinator

scombinator.md

The Connection between Apply and S combinator

I recently came across a video (https://youtu.be/UogkQ67d0nY?t=703) that looked at a problem and compared the solutions in Scala and Haskell.

The scala solution:

def maximumDifference(nums: Array[Int]): Int =
    nums.scanLeft(Int.MaxValue)(_ min _)
        .tail
        .zip(nums)
        .map(x => x._2 - x._1)
        .filter(_ != 0)
        .foldLeft(-1)(_ max _)

The haskell solution:

maximumDifference
    = foldl max (-1)
    . filter (/= 0)
    . (zipWith (-) <*> scanl1 min)

Breaking things up

The (zipWith (-) <*> scanl1 min) part confused me at first. I thought, “Maybe if I could find out the types I might be able to understand it?” Let's break the line up into zipWith (-) and scanl1 min.

For scanl1 min, the type of scanl1 is (a -> a -> a) -> [a] -> [a] and the type of min is (simplified) Int -> Int -> Int. Therefore, the type of scanl1 min is [Int] -> [Int].

For zipWith (-), the type of zipWith is (a -> b -> c) -> [a] -> [b] -> [c] and the type of (-) is (simplified) Int -> Int -> Int. Therefore, the type of zipWith (-) is [Int] -> [Int] -> [Int].

Now the tricky part: What does the <*> do? The first time I came across this operator was on the F# for fun and profit website where it was introduced as the infix operator for the apply function. The type of the apply function is f (a -> b) -> f a -> f b. In other words it takes a function (a -> b) that is wrapped inside an f and returns a function that takes an f a and returns an f b.

Confusion

My first assumption was that f is list. This would mean apply would be a function with the type [(a -> b)] -> [a] -> [b]. But this would not work with arguments [Int] -> [Int] -> [Int] and [Int] -> [Int].

Aha moment

When I found out that f can also be ((->) r) I had my aha moment. As a result, the type of apply is:

(r -> (a -> b)) -> (r -> (a)) -> (r -> (b))
(r -> a -> b) -> (r -> a) -> (r -> b)

Given arguments ([Int] -> [Int] -> [Int]) and ([Int] -> [Int]) the result of (zipWith (-) <*> scanl1 min) is ([Int] -> [Int]). I came up with the following implementation in F# which seemed after familiar watching the video:

let apply (f:'r->'a->'b) (x:'r->'a) (u:'r):'b =
    f u (x u)