4_b_8 and 4_b_9: Add solutions

2 files changed, 109 insertions, 2 deletions

diff --git a/README.md b/README.md
index c734f3d..9cfae0a 100644
--- a/README.md
+++ b/README.md
@@ -79,8 +79,8 @@ more visible in the list the first exercise of a group is in bold italics.
 | 4_b_5          | yes, in 4_b_6 |      | |
 | 4_b_6          | yes    |      | |
 | 4_b_7          | yes    |      | |
-| 4_b_8          |        |      | |
-| 4_b_9          |        |      | |
+| 4_b_8          | yes, in 4_b_9 |      | |
+| 4_b_9          | yes    |      | |
 | 4_b_10         |        |      | |
 | **_5_a_1_**    |        | 130  | 5. Writing a library: working with JSON data |
 | 5_a_2          |        |      | |
diff --git a/ch04/4_b_9.hs b/ch04/4_b_9.hs
new file mode 100644
index 0000000..baa7948
--- /dev/null
+++ b/ch04/4_b_9.hs
@@ -0,0 +1,107 @@
+-- 1. The Data.List module defines a function, groupBy, which has the following
+--    type:
+--
+--      -- file: ch04/ch04.exercises.hs
+--      groupBy :: (a -> a -> Bool) -> [a] -> [[a]]
+--
+-- 2. Use ghci to load the Data.List module and figure out what groupBy does,
+--    then write your own implementation using a fold.
+
+-- NOTE:
+--
+-- When I was solving this exercise for the first time, I tried the grouBy
+-- function only with (==) operator and came to a wrong conclusion about how it
+-- works. I thought that it compared current item to the previous one. After I
+-- had the solution implemented, I tried it with (<) operator and found a
+-- surprising result. That made me quite unsure about its behavior so I checked
+-- the Haskell documentation; groupBy actually compares to the first element in
+-- the group.
+--
+-- For completeness, I kept the wrong solution here. Then I went through this
+-- exercise again solving it as if I found the correct behavior only from trying
+-- different comparison operators and inputs.
+--
+-- Note that in general it is practically impossible to find out complete
+-- behavior of a function as a black box. We can only get closer to it, but we
+-- can never be completely sure without checking its implementation or reading a
+-- trusted documentation. For example, even though from
+--
+--   ghci> groupBy (<) [1, 2, 3, 2]
+--   [[1,2,3,2]]
+--   ghci> groupBy (<) [1, 2, 3, 1]
+--   [[1,2,3],[1]]
+--
+-- we could say that it compares to the first item in the group, but what if it
+-- compares like that only for a group up to 3 elements, and to the second item
+-- for a group of 4 and more elements. We could prove this by more experiments,
+-- but for an input list of unlimited size, we could come up with infinite
+-- amount of possible behaviors.
+
+wrongMyGroupBy :: (a -> a -> Bool) -> [a] -> [[a]]
+wrongMyGroupBy cmp xs = foldr op [] xs
+  where headCmp x (a:_) = cmp x a
+        op x [] = [[x]]
+        op x (a:as) = if headCmp x a
+                      then (x:a):as -- x is equal to the the head of the most
+                                    -- recent list (thus equal to all its items).
+                                    -- Add it to that list.
+                      else [x]:(a:as) -- x is not equal the head of the most
+                                      -- recent list. Start a new list.
+
+-- Let's try to find out what groupBy does by checking its type and output for
+-- different inputs.
+
+-- ghci> import Data.List
+-- ghci> :t groupBy
+-- groupBy :: (a -> a -> Bool) -> [a] -> [[a]]
+-- ghci> groupBy (==) []
+-- []
+-- ghci> groupBy (==) [1, 2, 3, 4, 5, 6]
+-- [[1],[2],[3],[4],[5],[6]]
+-- ghci> groupBy (==) [1, 1, 3, 4, 5, 6]
+-- [[1,1],[3],[4],[5],[6]]
+-- ghci> groupBy (==) [1, 1, 3, 4, 4, 6]
+-- [[1,1],[3],[4,4],[6]]
+-- ghci> groupBy (<) [1, 2, 3, 2]
+-- [[1,2,3,2]]
+-- ghci> groupBy (<) [1, 2, 3, 1]
+-- [[1,2,3],[1]]
+-- ghci> groupBy (<) [1, 2, 0, 1]
+-- [[1,2],[0,1]]
+
+-- groupBy seems to partition a list into sublists of adjacent items where all
+-- items in a sublist except the first one are compared with a 'true' result to
+-- the first item in that sublist.
+
+-- Left fold makes the implementation much easier because every sublist always
+-- (since it is added) contains the first value to compare the other values
+-- to. This is not the case with the right fold. When folding from the right and
+-- processing the elements one by one, we don't know which element is the first
+-- one to compare the other values in a sublist to, so processing an element may
+-- require splitting or merging the previous sublists.
+
+myGroupBy :: (a -> a -> Bool) -> [a] -> [[a]]
+myGroupBy cmp xs = foldl op [] xs
+  where headCmp (a:_) x = cmp a x
+        op [] x = [[x]]
+        op as x = if headCmp (last as) x
+                  then (init as) ++ [(last as) ++ [x]]
+                  else as ++ [[x]]
+
+-- ghci> :l 4_b_9.hs
+-- [1 of 1] Compiling Main             ( 4_b_9.hs, interpreted )
+-- Ok, one module loaded.
+-- ghci> myGroupBy (==) []
+-- []
+-- ghci> myGroupBy (==) [1, 2, 3, 4, 5, 6]
+-- [[1],[2],[3],[4],[5],[6]]
+-- ghci> myGroupBy (==) [1, 1, 3, 4, 5, 6]
+-- [[1,1],[3],[4],[5],[6]]
+-- ghci> myGroupBy (==) [1, 1, 3, 4, 4, 6]
+-- [[1,1],[3],[4,4],[6]]
+-- ghci> myGroupBy (<) [1, 2, 3, 2]
+-- [[1,2,3,2]]
+-- ghci> myGroupBy (<) [1, 2, 3, 1]
+-- [[1,2,3],[1]]
+-- ghci> myGroupBy (<) [1, 2, 0, 1]
+-- [[1,2],[0,1]]