Mappers.hs

{- 

A German blog post translating Java code for the build tool Ant to Scala

    http://funktionale-programmierung.de/2013/02/26/scala-java-ant.html

made me translate the Scala code to Haskell. I added combinators for binary
composition of mappers as well as a unit mapper for one of them. The code is
still shorter. I find the Haskell version more readable because expressions
and their types are separate rather than interleaved as in Scala.

Defining binary operators where the Scala version only had variants on lists
reveals algebraic properties that can be used to reason about mappers without
considering their implementation.

-}


module Mappers where


import Data.List (elemIndices)


type Mapper = String -> [String]


{- 

The combinator `&&&` composes two mappers by collecting their results in a
list. `discard` is its unit.

discard &&& m   = m
m &&& discard   = m

-}


discard :: Mapper
discard _ = []


(&&&) :: Mapper -> Mapper -> Mapper
(l &&& r) s = l s ++ r s


{-

The combinator `>>>` chains two mappers by applying the second mapper to every
result of the first and collecting all results. `identity` is its unit.

identity >>> m  = m
m >>> identity  = m

-}


identity :: Mapper
identity s = [s]


(>>>) :: Mapper -> Mapper -> Mapper
l >>> r = concatMap r . l


{-

Both `&&&` and `>>>` are associative operators.

a &&& (b &&& c) = (a &&& b) &&& c
a >>> (b >>> c) = (a >>> b) >>> c

-}


composite :: [Mapper] -> Mapper
composite = foldr (&&&) discard


chained :: [Mapper] -> Mapper
chained = foldr (>>>) identity


{-

`discard` is a zero of `>>>`.

discard >>> m   = discard
m >>> discard   = discard

Composition distributes over chaining from the right.

(a &&& b) >>> c = (a >>> c) &&& (b >>> c)

It distributes from the left, if we ignore the order of computed results.

sort . (a >>> (b &&& c)) = sort . ((a >>> b) &&& (a >>> c))

-}


glob :: String -> String -> Mapper
glob fromPat toPat =
    \s -> [ toPre ++ mid ++ toPost
          | let (pre, rest) = splitAt (length fromPre) s
                (mid, post) = splitAt (length rest - length fromPost) rest,
            pre == fromPre, post == fromPost ]
  where
    (fromPre, fromPost) = splitAtLastStar fromPat
    (toPre, toPost)     = splitAtLastStar toPat

    splitAtLastStar s =
        case elemIndices '*' s of
            [] -> (s,"")
            ps -> (take (last ps) s, drop (last ps+1) s)


{-

We can reason as follows to simplify combined mappers:

        glob "Mapper.*" "Mappers.*" &&&
            (glob "*.scala" "*.hs" >>> glob "Mapper.*" "Mappers.*")
    =
        (identity >>> glob "Mapper.*" "Mappers.*") &&&
            (glob "*.scala" "*.hs" >>> glob "Mapper.*" "Mappers.*")
    = 
        (identity &&& glob "*.scala" "*.hs") >>> glob "Mapper.*" "Mappers.*"

-}

A previous revision incorrectly stated that the type Mapper forms a semiring under composition and chaining. It does not, because one of the distributive laws only holds if we ignore the order in which results are computed.