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)
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
.
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]
.
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)