diff options
| -rw-r--r-- | README.md | 2 | ||||
| -rw-r--r-- | ch04/4_b_10.hs | 106 |
2 files changed, 107 insertions, 1 deletions
@@ -81,7 +81,7 @@ more visible in the list the first exercise of a group is in bold italics. | 4_b_7 | yes | | | | 4_b_8 | yes, in 4_b_9 | | | | 4_b_9 | yes | | | -| 4_b_10 | | | | +| 4_b_10 | yes | | | | **_5_a_1_** | | 130 | 5. Writing a library: working with JSON data | | 5_a_2 | | | | | **_6_a_1_** | | 162 | 6. Using typeclasses | diff --git a/ch04/4_b_10.hs b/ch04/4_b_10.hs new file mode 100644 index 0000000..f148d4e --- /dev/null +++ b/ch04/4_b_10.hs @@ -0,0 +1,106 @@ +-- How many of the following Prelude functions can you rewrite using list folds? +-- +-- - any +-- - cycle +-- - words +-- - unlines +-- +-- For those functions where you can use either foldl' or foldr, which is more +-- appropriate in each case? + +-- Let's assume that rewriting here means using a fold function as the top-level +-- function, using its output directly as an output of a rewritten function, and +-- not using any recursion in the fold's step function. +-- +-- "Appropriate" is a vague term. It can mean appropriate with regards to +-- - processing an infinite input list, or +-- - lazy evaluation in the case of a finite input list, not evaluating +-- subexpressions when not necessary, or +-- - learning/teaching purpose, or +-- - natural way of thinking about the problem to solve (e.g, people +-- usually read books from the first page to the last one, not the other way +-- around), or +-- - ... +-- +-- For deciding between foldl' and foldr, let's assume only finite input lists. + +-- References: +-- +-- - This article helped me to understand how lazy evaluation works with foldr +-- https://elbauldelprogramador.com/org-posts/foldr-infinite-list-haskell.html +-- - Description of the words function +-- https://hackage.haskell.org/package/base-4.18.0.0/docs/Prelude.html#v:words +-- - Description of the unlines function +-- https://hackage.haskell.org/package/base-4.18.0.0/docs/Prelude.html#v:unlines + +import Data.Char + +-- Let's use foldr. It enables short-circuit evaluation, not continuing in +-- evaluation of the rest of the input if the first value for which the f +-- function is true is found. +myAny :: (a -> Bool) -> [a] -> Bool +myAny f xs = foldr op False xs + where op x acc = if f x + then True + else acc + +-- ghci> :l 4_b_10.hs +-- [1 of 1] Compiling Main ( 4_b_10.hs, interpreted ) +-- Ok, one module loaded. +-- ghci> any odd [] +-- False +-- ghci> any odd [2, 4, 6, 8] +-- False +-- ghci> any odd [2, 4, 7, 8] +-- True +-- ghci> myAny odd [] +-- False +-- ghci> myAny odd [2, 4, 6, 8] +-- False +-- ghci> myAny odd [2, 4, 7, 8] +-- True + + +-- The cycle function cannot be rewritten using the list folds. It outputs an +-- infinite list. The input is a finite list. For a finite list, the step +-- function is called finite number of times, so without using recursion, it is +-- not possible to generate an infinite output. + + +-- The words function cannot be rewritten using the list folds. For example, the +-- function must be able to transform " foo bar " into ["foo", "bar"]. With +-- using fold as we defined it for this exercise, it is not possible to handle +-- trailing (or leading; depending on whether we use foldl' or foldr) spaces. It +-- would be possible if we allowed post-processing the output of the fold, +-- trimming the trailing empty string. +-- +-- Without post-processing, we have to find a way of not adding a trailing empty +-- string into the output for the trailing spaces in the input. This could be +-- done either by adding the empty string only after encountering a non-space +-- character (and putting that character into that empty string), or by adding +-- it when encountering a space character (correctly handling multiple +-- successive spaces). +-- +-- With the first option, we would have to ignore input spaces because we expect +-- a new empty string to be added to the output on a non-space input character, +-- but this would result in putting every non-space character into its own +-- output list. +-- +-- With the second option, we would add an empty list into the output for the +-- last trailing space, but it would stay empty in the output when there is no +-- non-space character to be put into that list. + + +-- Let's use foldr to take advantage of lazy evaluation. +myUnlines :: [String] -> String +myUnlines xs = foldr op [] xs + where op x acc = x ++ "\n" ++ acc + +-- ghci> unlines [] +-- "" +-- ghci> unlines ["abc","","","def "] +-- "abc\n\n\ndef \n" +-- ghci> myUnlines [] +-- "" +-- ghci> myUnlines ["abc","","","def "] +-- "abc\n\n\ndef \n" |