Last active
December 14, 2015 08:48
-
-
Save sebfisch/5060428 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| {- | |
| 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] | |
| {- | |
| Mapper is a semiring. | |
| `&&&` is addition, `discard` is its unit. | |
| discard &&& m = m | |
| m &&& discard = m | |
| -} | |
| discard :: Mapper | |
| discard _ = [] | |
| (&&&) :: Mapper -> Mapper -> Mapper | |
| (l &&& r) s = l s ++ r s | |
| {- | |
| `>>>` is multiplication, `identity` is its unit. | |
| identity >>> m = m | |
| m >>> identity = m | |
| -} | |
| identity :: Mapper | |
| identity s = [s] | |
| (>>>) :: Mapper -> Mapper -> Mapper | |
| l >>> r = concatMap r . l | |
| {- | |
| Addition and multiplication are associative. | |
| 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 >>> discrad = discard | |
| Multiplication distributes over addition. | |
| a >>> (b &&& c) = (a >>> b) &&& (a >>> c) | |
| (a &&& b) >>> c = (a >>> c) &&& (b >>> 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 "*.java" "*.scala" &&& | |
| (glob "*.java" "*.scala" >>> glob "*.scala" "*.hs") | |
| = | |
| (glob "*.java" "*.scala" >>> identity) &&& | |
| (glob "*.java" "*.scala" >>> glob "*.scala" "*.hs") | |
| = | |
| (glob "*.java" "*.scala" >>> (identity &&& glob "*.scala" "*.hs")) | |
| -} |
Author
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
A previous revision incorrectly stated that the type
Mapperforms 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.