Wednesday, 30 September 2015

I stumbled upon a 'functional programming interview question' recently; and I came up with a really nice functional programming answer, so feel free to drop the quotes actually.

Question: Given 'n' and a stream of floats, return a stream of the running average of the most recent n elements. If there aren't n elements yet output the average of all the elements available.

I looked at the problem and my first thought was a scanl maintaining the sum, count and the last n elements, with an appropriate update function.
Something like:

`avg :: Int -> [Float] -> [Float]
avg b = map getAvg . tail . scanl f def 
      getAvg (x, _, _) = x
      def = (0, 0, [])
      f :: (Float, Int, [Float]) -> Float -> (Float, Int, [Float])
      f (_, 0, _) v = (v, 1, [v])
      f (avg, n', x:xs) v | n' == b = (avg - x/n + v/n, n', xs++[v])
                          | otherwise = (avg*n/(n+1) + v/(n+1.0), n'+1, x:xs++[v])
            n :: Float
            n = fi n'

fi = fromIntegral`

We could improve the update function by tracking the sum and calculating the average at the time of `getAvg`
`avg :: Int -> [Float] -> [Float]
avg b = map getAvg . tail . scanl f def 
      getAvg (x, n, _) = x/fi n
      def = (0, 0, [])
      f :: (Float, Int, [Float]) -> Float -> (Float, Int, [Float])
      f (_, 0, _) v = (v, 1, [v])
      f (s, n', x:xs) v | n' == b = (s - x + v, n', xs++[v])
                        | otherwise = (s + v, n'+1, x:xs++[v])`

While that's pretty functional what with the scanl but I want to improve it.
The inspiration: `avg(i) = (f(i) - f(i-n))/n(i)`

So what do we need in order to calculate the average at some random point in the stream?
The sum of the last n elements and the min(number of elements, n).

Let f(i) | i < 0 = 0
            | otherwise = sum of all elements upto the ith index.
Sum of the last n elements = f(i) - f(i-n)

In the spirit of Haskell we can combine these quite cleanly:
Sum of the elements: `f(i) = scanl (+) 0 l !! i`
Sum of the elements n elements back: `f(i-n) = replicate n 0 ++ f(i) !! i`
`let lSum = scanl (+) 0 l`
Sum of the last n elements : `f(i) - f(i-n) = zipWith (-) lSum (replicate n 0 ++ lSum) !! i`
Number of elements so far: `n(i) = map (fi . min n) [1..] !! i`
Average: `avg(i) = (f(i) - f(i-n))/n(i)`

Join 'em together:  
f :: Int -> [Float] -> [Float]
f n l = zipWith (/) (zipWith (-) lSum lSum') lLen where lLen = map (fi . min n) [1..] lSum = tail (scanl (+) 0 l) lSum' = replicate n 0 ++ lSum  
fi = fromIntegral 


Heavy lifting: Mountains out of molehills

Small post today on some lovely stuff, time to strut that elegant Haskell plumage;

The specific task:
I represent a grid: `type Grid = (Int -> Info, Int -> Info)`
where the two functions are: `row index -> row information, col index -> col information`.

I have a function that updates a particular location (row, index) in the grid that manifests with an update to the row/column information (the update may fail):
`update :: Info -> Maybe Info`

However if the update fails, the entire grid becomes inconsistent so I want to propagate that inconsistency up.
Thus the problem is to create a function `liftInfoEdit: (Int, Int) -> (Info -> Maybe Info) -> Grid -> Maybe Grid`
That's the outline, the corner pieces.

This is a pretty cool theme pervasive in Haskell: leverage existing machinery to raise a function editing a piece of information up through the layers of the structure containing that information.

The first thing to note is that the edit is identical and independent w.r.t. the row and column of the grid; therefore we split our ed `t` into two separate streams and then finally join them together:

`t :: (Int -> Info) -> Maybe (Int -> Info)
trans :: Grid -> Maybe Grid
trans = (liftA2 . liftA2) (uncurry (,)) (t***t) $ grid`

Now we need to define `t`.
So what we could do is go down the following path:
Turn `(Int -> Info)` to `(Int -> Maybe Info)`. What we would like to do at this point is `(Int -> Maybe Info) -> Maybe (Int -> Info)` however the tires simply squeal in the mud. We want a change on a small portion of the function to be reflected on the entirety of the function.

What we could do instead is, split our function up and then glue it back together. Before we go further, one abstraction for a function `a -> b` is a `set(a, b)`.
Splitting a function up ~ split up its domain into 'a' and the rest.
`splitUpF :: a -> (a -> b) -> ((a, b), a -> b)
splitUpF a f = ((a, f a), f)

mergeF :: Eq a => ((a, b), a -> b) -> a -> b
mergeF ((a, b), g) a' | a == a' = b
                      | otherwise = g a'`

We now have all the pieces, its time to put them together; its time to do the dance: the jig-saw.

setG (r, c) v = updateLine (Row r) c v >=> updateLine (Col c) r v

updateLine :: Line -> Ind -> Maybe Value -> Grid -> Maybe Grid
updateLine l j v grid = dimap isom1 (uncurry (liftA2 (curry isom2)))
                        (finalFunc *** Just)
                        $ grid
      isom1 = view (from iso1)
      isom2 = view iso1
      (info, cond) = grid l
      finalFunc :: (Line -> Info) -> Maybe (Line -> Info)
      finalFunc = splitUpF l >>>
                  (g *** Just) >>>
                  uncurry (liftA2 (curry mergeF))
      g = second h >>> uncurry (fmap . (,))
      h info = if cond info'
               then Just info
               else Nothing
            info' = info & rep %~ f
            f :: Digs -> Digs
            f p i | i == j = v
                  | otherwise = p i