[Haskell for CP] Introduction and our first problem
§ Basic Setup
My basic setup is heavily inspired by Brent Yorgey. First have a look at this blog for the basic template we’ll be using.
{-# LANGUAGE ParallelListComp #-}
import Control.Arrow -- for >>>
main :: IO ()
main = interact $ _
There are also a few basic problems at the end of the above blog. I recommend you first try to solve them before attempting the problem that I am presenting.
§ Literate Haskell
This entire blog post is a haskell file! You can find the file
here.
You can download the file and run it directy using runhaskell.
§ Warmup
Let us solve an easy problem to get started.
This is the B problem from an AtCoder beginner contest.
You have \(n\) gems, with values \(V_i\) and cost \(C_i\). You want to pick some such that total value minus total cost is maximized. So you basically pick the ones which have \(V_i > C_i\).
Let us parse the input.
main = interact process
process :: String -> String
process =
lines {- convert to a list of lines -}
>>> drop 1 {- first line contains N, we don't need it -}
>>> map words {- words splits a string into words. we run that over each line -}
>>> map (map read) {- read parses a string to any type -}
>>> solve
>>> show {- convert to string -}
-- Given a list of two lists, take pairwise differences, and add up the positive ones.
solve1 :: [[Int]] -> Int
solve1 [vs, cs] = sum contribs
where
pairs = zip vs cs {- zip [1,2,3] [4,5,6] = [(1,4), (2,5), (3,6)] -}
contrib (v, c) = max 0 (v - c)
contribs = map contrib pairs {- apply contrib on each pair -}
Let us try to simplify this, by rewriting a zip followed by a map
using a zipWith
-- f :: (a, b) -> c
-- f' :: a -> b -> c -- curried version of f
map f (zip xs ys) = zipWith f' xs ys
solve2 [vs, cs] = sum contribs
where
contrib' v c = max 0 (v - c)
contribs = zipWith contrib' vs cs
We can further simplify this by first computing the differences, then filtering out the negative ones.
solve3 [vs, cs] = sum contribs
where
contrib' v c = v - c
contribs = filter (> 0) (zipWith contrib' vs cs)
Notice that contrib' is exactly the subtraction operator (-)!
solve4 [vs, cs] = sum contribs
where
contribs = filter (> 0) (zipWith (-) vs cs)
Finally, the shortest code I could write:
solve [vs, cs] = sum . filter (> 0) $ zipWith (-) vs cs
-- or, can use list comprehension
solve' [vs, cs] = sum . filter (> 0) $ [ v - c | v <- vs | c <- cs ]
How slick is that!
§ Next Problem
Here’s the first problem I’ll be discussing: Money Sums from cses.fi. It is a very standard knapsack problem, but try to solve it using haskell. I’ll post the solution next to next Friday which is 13th November, 2020.
Feel free to discuss in the comments at the end of this page.
