Merge pull request #1619 from Kaiepi/challenge-057

Add Ben Davies' Idris solutions for challenge 57

4 files changed, 86 insertions, 0 deletions

diff --git a/challenge-057/ben-davies/Makefile b/challenge-057/ben-davies/Makefile
new file mode 100644
index 0000000000..0217c165a2
--- /dev/null
+++ b/challenge-057/ben-davies/Makefile
@@ -0,0 +1,26 @@
+IDRIS := idris
+LIB   := idris
+
+.PHONY: all clean distclean
+
+all: ch-1 ch-2
+
+${LIB}/ch-1.o: ${LIB}/ch-1.idr
+	${IDRIS} -p contrib -c -o $@ $?
+
+${LIB}/ch-2.o: ${LIB}/ch-2.idr
+	${IDRIS} -c -o $@ $?
+
+ch-1: ${LIB}/ch-1.o
+	${IDRIS} $? -o ch-1
+
+ch-2: ${LIB}/ch-2.o
+	${IDRIS} $? -o ch-2
+
+clean:
+	-rm ${LIB}/ch-1.o
+	-rm ${LIB}/ch-2.o
+
+distclean: clean
+	-rm ch-1
+	-rm ch-2
diff --git a/challenge-057/ben-davies/README.md b/challenge-057/ben-davies/README.md
index 77158344c9..9b706ecd09 100644
--- a/challenge-057/ben-davies/README.md
+++ b/challenge-057/ben-davies/README.md
@@ -1 +1,11 @@
 Solution by Ben Davies
+
+# Using the Solutions
+
+- Install
+  [Idris](https://github.com/idris-lang/Idris-dev/wiki/Installation-Instructions)
+  and ensure its executable is in your path.
+- Run `$ make -j2`. The executables for the challenges will be output to
+  `./ch-1` and `./ch-2`.
+- Run `$ make clean` to remove compiled objects or `$ make distclean` to
+  remove the executables as well, if you wish.
diff --git a/challenge-057/ben-davies/idris/ch-1.idr b/challenge-057/ben-davies/idris/ch-1.idr
new file mode 100644
index 0000000000..e5423a3ad2
--- /dev/null
+++ b/challenge-057/ben-davies/idris/ch-1.idr
@@ -0,0 +1,25 @@
+module Main
+
+import Data.String.Extra
+
+%default total
+
+data Tree a = Node a | Branch a (Tree a) (Tree a)
+
+private
+showTree : Show a => (n : Nat) -> (t : String) -> Tree a -> String
+showTree n t (Node a)       = indent (n * 2) t ++ " " ++ show a
+showTree n t (Branch a l r) = indent (n * 2) t ++ " " ++ show a ++ "\n" ++
+                              showTree (n + 1) "L" l ++ "\n" ++
+                              showTree (n + 1) "R" r
+
+implementation Show a => Show (Tree a) where
+    show = showTree 0 "T"
+
+-- Inverts a tree.
+invert : Tree a -> Tree a
+invert (Node a)       = Node a
+invert (Branch a l r) = Branch a (invert r) (invert l)
+
+main : IO ()
+main = printLn $ invert $ Branch 1 (Branch 2 (Node 4) (Node 5)) (Branch 3 (Node 6) (Node 7))
diff --git a/challenge-057/ben-davies/idris/ch-2.idr b/challenge-057/ben-davies/idris/ch-2.idr
new file mode 100644
index 0000000000..2b99ab3432
--- /dev/null
+++ b/challenge-057/ben-davies/idris/ch-2.idr
@@ -0,0 +1,25 @@
+module Main
+
+%default total
+
+-- Finds the longest unique prefix for the LHS in the RHS.
+prefixFor : (x : String) -> (y : String) -> String
+prefixFor x y = case head' $ dropWhile (`isPrefixOf` unpack y) (inits $ unpack x) of
+                     Nothing => ""
+                     Just cs => pack cs
+
+-- Given a list of words, finds the unique prefixes for a word.
+prefixesFor : (ws : List String) -> (w : String) -> List String
+prefixesFor ws w = (`prefixFor` w) <$> ws
+
+-- Given a list of words, finds the unique prefix for each word in the list.
+prefixes : (ws : List String) -> List String
+prefixes ws = foldr maxLength "" <$> transpose (prefixesFor ws <$> ws)
+    where maxLength : String -> String -> String
+          maxLength a b = if length b > length a then b else a
+
+wordList : List String
+wordList = ["alphabet", "book", "carpet", "cadmium", "cadeau", "alpine"]
+
+main : IO ()
+main = printLn $ prefixes wordList