Chapter 8: Recursion

“Recursion (rĭ-kûr’-zhən) noun. If you still don’t get it, see recursion.”

A recursive structure is one that contains a smaller instance of itself.

A process or structure is recursive when it contains progressively smaller nested instances of itself.

“An object is said to be recursive if it partially consists or is defined in terms of itself.”

~ Niklaus Wirth. Algorithms + Data Structures = Programs. ISBN-13: 978-0130224187.

“An entity or concept is said to be recursive when simpler or smaller self-similar instances form part of its constituents.”

~ Manuel Rubio-Sánchez. Introduction to Recursive Programming. ISBN-13: 978-1-4987-3528-5.

“The recursive problem solving process can be described loosely as follows:

• If the given instance of the problem can be solved directly, do so.

• Otherwise, reduce it to one or more smaller instances of the same problem.”

~ Jeff Erickson. Algorithms. ISBN-13: 978-1792644832.

“The power of recursion evidently lies in the possibility of defining an infinite set of objects by a finite statement. In the same manner, an infinite number of computations can be described by a finite recursive program, even if this program contains no explicit repetitions.”

~ Niklaus Wirth. Algorithms + Data Structures = Programs. ISBN-13: 978-0130224187.

“Recursion is the root of computation since it trades description for time.”

~ Alan Perlis. Epigrams on Programming.

8.1 Recursion

Unifing control-flow and data-flow

Function calls are the only mechanism for control flow in Haskell. They’re also the only mechanism for changing values. This effectively means that the control flow and data flow of a program are the same; both control and data go from function call to function call. Rather than having a separate graph for the control flow and data flow of a program, there is one graph that represents both. This makes execution of a Haskell program less like updating registers of a machine that advances a program counter, and more like evaluating a system of equations in algebra.

Recursive function definitions without a name

Paragraph three asks this question: How do we define a recursive anonymous function? Doesn’t the function need a name so that it can call itself?

One workaround is to provide a duplicate of the function as an input argument value, which is then bound to a parameter name so that it can be called within the function definition, like so:

·∾  import Data.Function (fix)

·∾ -- Fix duplicates the function and feeds
·∾ -- it to itself as the first argument.

·∾  fix (\f n -> if n == 0 then 1 else n * f (n-1)) 3
6

·∾ import Unsafe.Coerce (unsafeCoerce)

·∾ -- Fix, above, corresponds to the Y-combinator
·∾ -- in lambda calculus, but the definition is
·∾ -- pretty different. It looks like
·∾ -- fix f = let x = f x in x. The lambda calculus
·∾ -- version looks like (λy.(λx.y(xx))(λx.y(xx))).

·∾ -- Using unsafeCoerce we can write a definition
·∾ -- of the Y-combinator that corresponds closely
·∾ -- to that found in untyped lambda calculus.

·∾ uc = unsafeCoerce

·∾ :{
 ⋮ (\y -> (\x -> y (uc x x)) (\x -> y (uc x x)))
 ⋮ (\f n -> if n == 0 then 1 else n * f (n-1))
 ⋮ 6
 ⋮ :}
6

·∾ :{
 ⋮ (\f -> (\x -> f (uc x x)) (\x -> f (uc x x)))
 ⋮ (\f n -> if n == 0 then 1 else n * f (n-1))
 ⋮ 20
 ⋮ :}
2432902008176640000

In this chapter, we will:

• explore what recursion is and how recursive functions evaluate;

• go step-by-step through the process of writing recursive functions;

• have fun with bottom.

8.2 Factorial!

Let’s examine a simple factorial function:

factorial 0 = 1
factorial n = n * factorial (n - 1)

Recursive functions are comprised of two categories of input cases: base cases and recursive cases. A recursive function can contain any number of base cases, but must have at least one recursive case.

Base cases are where a functions output value can be obtained without requiring further recursive calls. In the factorial function declaration above, the base case is written as the equation factorial 0 = 1. Technically, the input value 0 is the base case, and 1 is the value that corresponds to it. In the case of 0, we return 1. If you think of recursive calls as inductive reasoning steps, the base case forms the basis for those inferences.

Recursive cases are where self-referencing function calls occur. A recursive call applies the function definition to different input values. Each call of the function splits the input into smaller values of that function. Theses values are then combined to arrive at the final answer. In our function declaration, the recursive case is the equation factorial n = n * factorial (n - 1).

In order for function evaluation to eventually stop, each recursive call of this case should move progressively closer towards one of the base cases. If not, the function will call itself forever, a phenomena know as infinite recursion.

Here is an example of how factorial 4 evaluates:

factorial 0 = 1
factorial n = n * factorial (n - 1)

-- The ==> symbol indicates a new step in the reduction process. Each call of
-- ⧼factorial arg⧽ is replaced with its definition, where ⧼n⧽ has been replaced
-- by the current argument.

factorial 4 ==> 4 * factorial (4 - 1)
            ==> 4 * (4 - 1) * factorial ((4 - 1) - 1)
            ==> 4 * (4 - 1) * ((4 - 1) - 1) * factorial (((4 - 1) - 1) - 1)
            ==> 4 * (4 - 1) * ((4 - 1) - 1) * (((4 - 1) - 1) - 1) * factorial ((((4 - 1) - 1) - 1) - 1)
            --                                                                ^^^^^^^^^^^^^^^^^^^^^^^^^
            --                                       The base case is triggered here.
            --                                                      v
            ==> 4 * (4 - 1) * ((4 - 1) - 1) * (((4 - 1) - 1) - 1) * 1
            ==> 4 * 3 * 2 * 1 * 1
            ==> 4 * 3 * 2 * 1
            ==> 4 * 3 * 2
            ==> 4 * 6
            ==> 24

If we didn’t supply the base case 0 -> 1, then the recursive call would never stop, subtracting forever.

8.2.1 Another way to look at recursion

Here’s another example, to show how building up the call stack resembles composing multiple instances of the same function (this is a combination of figures 8 and 9):

applyTimes :: (Eq a, Num a) => a -> (b -> b) -> b -> b
applyTimes 0 f b = b
applyTimes n f b = f (applyTimes (n-1) f b)

incTimes' :: (Eq a, Num a) => a -> a -> a
incTimes' times n = applyTimes times (+1) n

applyTimes :: (Eq a, Num a) => a -> (b -> b) -> b -> b
applyTimes 0 f b  =  b
applyTimes n f b  =  f . applyTimes (n-1) f $ b
--                     ^
--  Building up the series of self-referential function compositions...

8.2.2 Intermission: Exercise

Write out the evaluation of applyTimes 5 (+1) 5. It might be a little less noisy if you do so with the form that doesn’t use the composition operator, (.).

With the definition of applyTimes that doesn’t use composition:

applyTimes 0 f b    =  b
applyTimes n f b    =  f (applyTimes (n-1) f b)

Reduction steps:

applyTimes 5 (+1) 5  =  (+1) (applyTimes (5-1) (+1) 5)
applyTimes 4 (+1) 5  =  (+1) ((+1) (applyTimes (4 -1) (+1) 5))
applyTimes 3 (+1) 5  =  (+1) ((+1) ((+1) (applyTimes (3 -1) (+1) 5)))
applyTimes 2 (+1) 5  =  (+1) ((+1) ((+1) ((+1) (applyTimes (2 -1) (+1) 5))))
applyTimes 1 (+1) 5  =  (+1) ((+1) ((+1) ((+1) ((+1) (applyTimes (1 -1) (+1) 5)))))
applyTimes 0 (+1) 5  =  (+1) ((+1) ((+1) ((+1) ((+1) 5))))
                     =  (+1) ((+1) ((+1) ((+1) 6)))
                     =  (+1) ((+1) ((+1) 7))
                     =  (+1) ((+1) 8)
                     =  (+1) 9
                     =  10

Using composition this time. First I’ll provide the definition for context:

applyTimes :: (Eq a, Num a) => a -> (b -> b) -> b -> b
applyTimes 0 f b  =  b
applyTimes n f b  =  f . applyTimes (n-1) f $ b

Now to show the reduction steps:

applyTimes 5 (+1) 5  =  (+1) . applyTimes (5-1) (+1) $ 5
applyTimes 4 (+1) 5  =  (+1) . (+1) . applyTimes (4-1) (+1) $ 5
applyTimes 3 (+1) 5  =  (+1) . (+1) . (+1) applyTimes (3-1) (+1) $ 5
applyTimes 2 (+1) 5  =  (+1) . (+1) . (+1) . (+1) . applyTimes (2-1) (+1) $ 5
applyTimes 1 (+1) 5  =  (+1) . (+1) . (+1) . (+1) . (+1) . applyTimes (1-1) (+1) $ 5
applyTimes 0 (+1) 5  =  (+1) . (+1) . (+1) . (+1) . (+1) $ 5
                     =  (+1) . (+1) . (+1) . (+1) $  6
                     =  (+1) . (+1) . (+1) $  7
                     =  (+1) . (+1) $  8
                     =  (+1) $  9
                     =   10

I think this version is easier to read. At least there are fewer parenthesis.

8.3 Bottom

⊥, or bottom, denotes computations that don’t successfully result in a value. The two main varieties of bottom are computations that failed with an error or those that failed to terminate (for example, and infinite loop). In logic ⊥ corresponds to False.

Non-termination

Here’s a non-terminating expression. When we run it, GHCi gets stuck in an infinite loop:

·∾ let x = x in x
^CInterrupted.

With a different version of GHC, the expression let x = x in x may have resulted in an exception, instead of heating up my laptop until I pressed Control-c.

Partial functions

Another source of bottom are partial functions. For example:

·∾ :{
 ⋮ f :: Bool -> Int
 ⋮ f False = 0
 ⋮ :}
·∾
·∾ f False
0
·∾ f True
*** Exception: <interactive>:3:1-11: Non-exhaustive patterns in function f

In order to defend against this, we can define a catch-all case. Or, if it doesn’t make sense to do so, we can explicitly return nothing, using the Maybe data type, like this:

·∾ :{
 ⋮ f :: Bool -> Maybe Int
 ⋮ f False = Just 0
 ⋮ f _     = Nothing
 ⋮ :}
·∾
·∾ f True
Nothing
·∾ f False
Just 0

Undefined values

What happens if we try to evaluate undefined in the repl?

·∾ undefined
*** Exception: Prelude.undefined
CallStack (from HasCallStack):
  error, called at libraries/base/GHC/Err.hs:80:14 in base:GHC.Err
  undefined, called at <interactive>:22:1 in interactive:Ghci9

Intentionally thrown errors

Another source of bottom values are intentionally thrown errors. The function error prints a string and returns undefined.

·∾ error "Should this be in a monad?"
*** Exception: Should this be in a monad?
CallStack (from HasCallStack):
  error, called at <interactive>:27:1 in interactive:Ghci9

8.4 Fibonacci numbers

8.4.1 Consider the types

Why didn’t the authors use Natural?

The Fibonacci function we’re defining only works on positive numbers, so it makes more sense to use a type that can only represent positive integers, like Natural or Word. Why didn’t the authors do that?

Probably to avoid discussing the mechanics of how negative numeric literals are resolved to values by GHC.

When GHC evaluates an expression like (-10), it does not immediately turn it into a number with the value \(-10\), but instead desugurs it into (negate 10). At this point, negate tries to turn a value 10 to (-10) of type Natural, but it can’t, so it throws an exception if done at runtime. If we try compiling a file with this expression, instead, we’ll get a warning and it won’t compile. I was expecting a type error, instead.

I’m still confused, and I’ll have to read up on this. But hey, I learned something new!

https://downloads.haskell.org/~ghc/latest/docs/html/users_guide/exts/lexical_negation.html#extension-LexicalNegation

Can I write a better type signature for Fibonacci?

Here’s an article about writing a proof for Fibonacci in a LiquidHaskell type annotation. https://ucsd-progsys.github.io/liquidhaskell-blog/2016/09/18/refinement-reflection.lhs/

8.5 Integral division from scratch

Here’s an example for integral division. The inner go function keeps a count that the outer dividedBy function doesn’t care about:

module DividedBy (dividedBy) where

dividedBy :: Integral a => a -> a -> (a, a)
dividedBy num denom = go num denom 0
  where go n d count
          |     n < d = (count, n)
          | otherwise = go (n - d) d (count + 1)

8.6 Chapter Exercises

8.6.1 Review of types

1. What is the type of [[True, False], [True, True], [False, True]]?

   1. Bool

   2. mostly True

   3. [a]

   4. [[Bool]]

      Here’s the proof:

      ·∾ :type [[True, False], [True, True], [False, True]]
      [[True, False], [True, True], [False, True]] :: [[Bool]]
      

2. Which of the following has the same type as [[True, False], [True, True], [False, True]]?

   1. [(True, False), (True, True), (False, True)]

   2. [[3 == 3], [6 > 5], [3 < 4]]

      Have some proof!

      ·∾ :type [[True, False], [True, True], [False, True]]
      [[True, False], [True, True], [False, True]] :: [[Bool]]
      
      ·∾ :type [[3 == 3], [6 > 5], [3 < 4]]
      [[3 == 3], [6 > 5], [3 < 4]] :: [[Bool]]
      

   3. [3 == 3, 6 > 5, 3 < 4]

   4. ["Bool", "more Bool", "Booly Bool!"]

3. For the following function

   func :: [a] -> [a] -> [a]
   func x y = x ++ y
   

   …which of the following is true?

   1. x and y must be of the same type

      Yes, the a within the type signature here denotes the same type for both parameters, as well as the return type.

   2. x and y must both be lists

      Yup. Each parameter has type [a] or “list of a”.

   3. if x is a String then y must be a String

      This is true, too. Here is the proof:

      ·∾ :type func "The value of param x"
      func "The value of param x" :: [Char] -> [Char]
      

   4. all of the above

4. For the following code, which is a valid application of func to both of its arguments?

   func :: [a] -> [a] -> [a]
   func x y = x ++ y
   

   1. func "Hello World"

      This will return a partially applied function, with one parameter left unsaturated.

      Here’s what happens when you try it in GHCi:

      ·∾ func "Hello World"
      
      <interactive>:30:1: error:
          • No instance for (Show ([Char] -> [Char]))
              arising from a use of ‘print’
              (maybe you haven't applied a function to enough arguments?)
          • In a stmt of an interactive GHCi command: print it
      

   2. func “Hello” “World”

      This saturates both parameters with values.

      ·∾ func "Hello" "World"
      "HelloWorld"
      

   3. func [1, 2, 3] "a, b, c"

      This won’t work, since each argument has a different type, and func requires that they both be of the same type. Here’s what happens when I try:

      ·∾ func [1, 2, 3] "a, b, c"
      
      <interactive>:32:7: error:
          • No instance for (Num Char) arising from the literal ‘1’
          • In the expression: 1
            In the first argument of ‘func’, namely ‘[1, 2, 3]’
            In the expression: func [1, 2, 3] "a, b, c"
      

   4. func ["Hello", "World"]

      This has only one argument.

      ·∾ func ["Hello", "World"]
      
      <interactive>:33:1: error:
          • No instance for (Show ([[Char]] -> [[Char]]))
              arising from a use of ‘print’
              (maybe you haven't applied a function to enough arguments?)
          • In a stmt of an interactive GHCi command: print it
      

8.6.2 Reviewing currying

Given the following definitions, tell us what value results from further applications.

module Lib where


-- _(++" mrow "++)_
cattyConny :: String -> String -> String
cattyConny x y = x ++ " mrow " ++ y


flippy :: String -> String -> String
flippy = flip cattyConny


-- ("woops mrow"++)_
appedCatty :: String -> String
appedCatty = cattyConny "woops"


-- _(++" mrow haha")
frappe :: String -> String
frappe = flippy "haha"

1. What is the value of appedCatty "woohoo!"? Try to determine the answer for yourself, then test in the REPL.

   Ok, desk-checking time:

   >>> appedCatty "woohoo!"
   >>> (cattyConny "woops") "woohoo!"
   >>> ((\x y -> x ++ " mrow " ++ y) "woops") "woohoo!"
   >>> (\y -> "woops" ++ " mrow" ++ y) "woohoo!"
   >>> "woops" ++ " mrow" ++ "woohoo!"
   >>> "woops mrowwoohoo!"
   

   My test looks like this:

   
       it "appedCatty \"woohoo!\" ==> \"woops mrow woohoo!\"" $ do
         appedCatty "woohoo!" `shouldBe` "woops mrow woohoo!"
   
   

   …and here is what happens when I run it:

   $ pwd
   /home/chris/Projects/hpfp/08_-_recursion/exercises/8.6.2_-_reviewing_currying.rst.d/currying
   
   $ stack test --test-arguments='--match "Question 1"' --verbosity silent
   
   Question 1
     appended to the end
   
   Finished in 0.0003 seconds
   1 example, 0 failures
   

2. frappe "1"

   Let me think about this:

   >>> frappe "1"
   >>> (flippy "haha") "1"
   >>> ((flip cattyConny) "haha") "1"
   >>> ((flip (\x y -> x ++ " mrow " ++ y)) "haha") "1"
   >>> ((\y x -> x ++ " mrow " ++ y) "haha") "1")
   >>> (\x -> x ++ " mrow " ++ "haha") "1"
   >>> "1" ++ " mrow " ++ "haha"
   >>> "1 mrow haha"
   

   Here’s what my test looks like:

   
       it "frappe \"1\" ==> \"1 mrow haha\"" $ do
         frappe "1" `shouldBe` "1 mrow haha"
   
   

   Time to test:

   $ stack test --test-arguments='--match "Question 2"' --verbosity silent
   
   Question 2
     frappe "1" ==> "1 mrow haha"
   
   Finished in 0.0004 seconds
   1 example, 0 failures
   

3. frappe (appedCatty "2")

   Unpacking indirection:

   >>> frappe (appedCatty "2")
   >>> frappe ((cattyConny "woops") "2")
   >>> frappe (((\x y -> x ++ " mrow " ++ y) "woops") "2")
   >>> (flippy "haha") (((\x y -> x ++ " mrow " ++ y) "woops") "2")
   >>> ((flip cattyConny) "haha") (((\x y -> x ++ " mrow " ++ y) "woops") "2")
   >>> ((flip (\x y -> x ++ " mrow " ++ y)) "haha") (((\x y -> x ++ " mrow " ++ y) "woops") "2")
   >>> ((\y x -> x ++ " mrow " ++ y) "haha") (((\x y -> x ++ " mrow " ++ y) "woops") "2")
   >>> (\x -> x ++ " mrow " ++ "haha") (((\x y -> x ++ " mrow " ++ y) "woops") "2")
   >>> (\x -> x ++ " mrow " ++ "haha") ((\y -> "woops" ++ " mrow " ++ y) "2")
   >>> (\x -> x ++ " mrow " ++ "haha") ("woops" ++ " mrow " ++ "2")
   >>> (\x -> x ++ " mrow " ++ "haha") "woops mrow 2"
   >>> "woops mrow 2" ++ " mrow " ++ "haha"
   >>> "woops mrow 2 mrow haha"
   

   Here is the test case:

   
       it "frappe (appedCatty \"2\") ==> \"woops mrow 2 mrow haha\"" $ do
         frappe (appedCatty "2") `shouldBe` "woops mrow 2 mrow haha"
   
   

   Now to test it out. I hope I didn’t do all that typing for nothing:

   $ stack test --test-arguments='--match "Question 3"' --verbosity silent
   Progress 1/2: currying
   Question 3
     frappe (appedCatty "2") ==> "woops mrow 2 mrow haha"
   
   Finished in 0.0002 seconds
   1 example, 0 failures
   

   I should see if there is an editor plugin to replace functions with their definitions.

4. appedCatty (frappe "blue")

   I’ll try to do this one in my head. It should result in "woops mrow blue mrow haha"? Maybe?

   No, I better write it out:

   >>> appedCatty (frappe "blue")
   >>> appedCatty ((flippy "haha") "blue")
   >>> appedCatty (((flip cattyConny) "haha") "blue")
   >>> appedCatty (((flip (\x y -> x ++ " mrow " ++ y) "haha") "blue")
   >>> appedCatty (((\y x -> x ++ " mrow " ++ y) "haha") "blue")
   >>> (cattyConny "woops") (((\y x -> x ++ " mrow " ++ y) "haha") "blue")
   >>> ((\x y -> x ++ " mrow " ++ y) "woops") (((\y x -> x ++ " mrow " ++ y) "haha") "blue")
   >>> (\y -> "woops" ++ " mrow " ++ y) (((\y x -> x ++ " mrow " ++ y) "haha") "blue")
   >>> (\y -> "woops" ++ " mrow " ++ y) ((\x -> x ++ " mrow " ++ "haha") "blue")
   >>> (\y -> "woops" ++ " mrow " ++ y) ("blue" ++ " mrow " ++ "haha")
   >>> (\y -> "woops" ++ " mrow " ++ y) "blue mrow haha"
   >>> "woops" ++ " mrow " ++ "blue mrow haha"
   >>> "woops mrow blue mrow haha"
   

   Here is the test case:

   
       it "appedCatty (frappe \"blue\") ==> \"woops mrow blue mrow haha\"" $ do
         appedCatty (frappe "blue") `shouldBe` "woops mrow blue mrow haha"
   
   

   Now to test it:

   $ stack test --test-arguments='--match "Question 4"' --verbosity silent
   Progress 1/2: currying
   Question 4
     appedCatty (frappe "blue") ==> "woops mrow blue mrow haha"
   
   Finished in 0.0004 seconds
   1 example, 0 failures
   

5. cattyConny (frappe "pink") (cattyConny "green" (appedCatty "blue"))

   I’m getting tired, now, so I skipped a few steps:

   >>> cattyConny (frappe "pink") (cattyConny "green" (appedCatty "blue"))
   >>> (\y -> (frappe "pink") ++ " mrow " ++ y) (cattyConny "green" (appedCatty "blue"))
   >>> frappe "pink" ++ " mrow " ++ (cattyConny "green" (appedCatty "blue"))
   >>> frappe "pink" ++ " mrow " ++ ("green" ++ " mrow " ++ ("woops" ++ " mrow " ++  "blue"))
   >>> frappe "pink" ++ " mrow green mrow woops mrow blue"
   >>> (flippy "haha") "pink" ++ " mrow green mrow woops mrow blue"
   >>> ((flip cattyConny) "haha") "pink" ++ " mrow green mrow woops mrow blue"
   >>> (\x -> x ++ " mrow " ++ "haha") "pink" ++ " mrow green mrow woops mrow blue"
   >>> "pink" ++ " mrow " ++ "haha" ++ " mrow green mrow woops mrow blue"
   >>> "pink mrow haha mrow green mrow woops mrow blue"
   

   Here’s the test case:

   
       it "cattyConny (frappe \"pink\") (cattyConny \"green\" (appedCatty \"blue\")) \
          \ ==> \
          \\"pink mrow haha mrow green mrow woops mrow blue\"" $ do
         cattyConny (frappe "pink") (cattyConny "green" (appedCatty "blue"))
           `shouldBe` "pink mrow haha mrow green mrow woops mrow blue"
   
   

   Results of the test:

   $ stack test --test-arguments='--match "Question 5"' --verbosity silent
   Progress 1/2: currying
   Question 5
     cattyConny (frappe "pink") (cattyConny "green" (appedCatty "blue"))  ==>  "pink mrow haha mrow green mrow woops mrow blue"
   
   Finished in 0.0002 seconds
   1 example, 0 failures
   

6. cattyConny (flippy "Pugs" "are") "awesome"

   Reduction:

   >>> cattyConny (flippy "Pugs" "are") "awesome"
   >>> (flippy "Pugs" "are") ++ " mrow " ++ "awesome"
   >>> ("are" ++ " mrow " ++ "Pugs") ++ " mrow " ++ "awesome"
   >>> "are mrow Pugs mrow awesome"
   

   Test case:

   
       it "cattyConny (flippy \"Pugs\" \"are\") \"awesome\"\
          \ ==> \
          \\"are mrow Pugs mrow awesome\"" $ do
         cattyConny (flippy "Pugs" "are") "awesome" `shouldBe` "are mrow Pugs mrow awesome"
   

   Proof:

   $ stack test --test-arguments='--match "Question 6"' --verbosity silent
   
   Question 6
     cattyConny (flippy "Pugs" "are") "awesome" ==> "are mrow Pugs mrow awesome"
   
   Finished in 0.0007 seconds
   1 example, 0 failures
   

8.6.3 Recursion

1. Write out the steps for reducing dividedBy 15 2 to its final answer according to the Haskell code.

   First let’s show the definition of that function.

   module DividedBy where
   
   dividedBy :: Integral a => a -> a -> (a, a)
   dividedBy num denom =
     go num denom 0
     where
       go n d count
         | n < d = (count, n)
         | otherwise = go (n - d) d (count + 1)
   

   Now for the evaluation

   dividedBy 15 2 =
     go 15 2 0
     where
       go 15 2 0
         | 15 < 2 = (0, 15)
   -->   | otherwise = go (15 - 2) 2 (0 + 1)
   
       go 13 2 1
         | 13 < 2 = (1, 13)
   -->   | otherwise = go (13 - 2) 2 (1 + 1)
   
       go 11 2 2
         | 11 < 2 = (2, 11)
   -->   | otherwise = go (11 - 2) 2 (2 + 1)
   
       go 9 2 3
         | 9 < 2 = (3, 9)
   -->   | otherwise = go (9 - 2) 2 (3 + 1)
   
       go 7 2 4
         | 7 < 2 = (4, 7)
   -->   | otherwise = go (7 - 2) 2 (4 + 1)
   
       go 5 2 5
         | 5 < 2 = (5, 5)
   -->   | otherwise = go (5 - 2) 2 (5 + 1)
   
       go 3 2 6
         | 3 < 2 = (6, 3)
   -->   | otherwise = go (3 - 2) 2 (6 + 1)
   
       go 1 2 7
   -->   | 1 < 2 = (7, 1)
         | otherwise = go (1 - 2) 2 (7 + 1)
   
   dividedBy 15 2 = (7,1)
   

2. Write a function that recursively sums all numbers from 1 to n. The type should be :: (Eq a, Num a) => a -> a.

   {-# OPTIONS_GHC -fwarn-incomplete-patterns #-}
   module Lib (sumTo) where
   
   -- Because GHC doesn't know that signum can only return 1, -1, or
   -- 0, it assumes that any number representable by Int may be the
   -- result, so the fallback case is necessary to suppress our
   -- warning.
   sumTo :: (Eq a, Num a) => a -> a
   sumTo n = case signum n of
     (-1) -> n + sumTo (n+1)
     1    -> n + sumTo (n-1)
     0    -> 0
     _    -> error "sumTo received an invalid input"
   

   Here is the test suite, for your perusal.

   import Test.Hspec
   import Lib (sumTo)
   
   main = hspec $ do
     describe "sumTo" $ do
       it "sums 1..12" $ do
         sumTo 12 `shouldBe` sum [1..12]
       it "negative values for n enumarate from (-1),(-2)..n" $ do
         sumTo (-20) `shouldBe` sum [(-1),(-2)..(-20)]
       it "returns 0 for 0" $ do
         sumTo 0 `shouldBe` 0
   

   You can test this by navigating to exercises/8.6.3_-_recursion.rst.d/sum-to and running stack test.

   I wasn’t sure what to do with negative inputs, so I made the function sum from (-1)..n. Maybe this is wrong.

3. Write a function that multiplies two integral numbers using recursive summation. The type should be :: Integral a => a -> a -> a.

   Code:

   module Lib (mult) where
   
   mult :: Integral a
        => a -> a -> a
   mult x y
     |        x == 0     =   0
     |        y == 0     =   0
     | signum y == 1     =   go x y 1
     | signum y == (-1)  =   negate $ go x (abs y) 1
     where
       go n m count
         | count == abs m  =  n
         | otherwise       =  go (n+x) m (count+1)
   
   --mult :: Integral a => a -> a -> a
   --mult x y =
   --  if signum y == (-1)
   --  then  negate . foldr (+) 0 . take (abs y) $ repeat x
   --  else           foldr (+) 0 . take (abs y) $ repeat x
   

   Test suite:

   import Test.Hspec
   import Lib (mult)
   
   main = hspec $ do
     describe "mult" $ do
       it "5 5 -> 25" $ do
         mult 5 5 `shouldBe` 25
       it "(-7) 2 -> (-14)" $ do
         mult (-7) 2 `shouldBe` (-14)
       it "10 (-2) -> (-20)" $ do
         mult 10 (-2) `shouldBe` (-20)
       it "(-10) (-2) -> 20" $ do
         mult (-10) (-2) `shouldBe` 20
       it "8 (-2) -> (-16)" $ do
         mult 8 (-2) `shouldBe` (-16)
       it "8 0 -> 0" $ do
         mult 8 0 `shouldBe` 0
       it "0 8 -> 0" $ do
         mult 0 8 `shouldBe` 0
   

8.6.4 Fixing dividedBy

Our dividedBy function wasn’t quite ideal. For one thing. It was a partial function and doesn’t return a result (bottom) when given a divisor that is 0 or less. Consider using the following datatype to handle division by 0

data DividedResult = Result Integer | DividedByZero

Here is my attempt. It’s rather messy and I don’t like it, but it works.

module Lib (dividedBy', DividedResult(..)) where

data DividedResult = Result Integer | DividedByZero deriving (Eq, Ord, Show)

dividedBy' :: Integer -> Integer -> DividedResult
dividedBy' num denom
  |                       signum denom == 0      =    DividedByZero
  |    signum num == 0 && signum denom /= 0      =    Result 0
  |    signum num == 1 && signum denom == 1      =    Result (num `divPlus` denom)
  | signum num == (-1) && signum denom == (-1)   =    Result (abs num `divPlus` abs denom)
  | signum num == (-1) || signum denom == (-1)   =    Result (num `divNeg` denom)
  where
    divPlus x y = fst $ dividedBy x y
    divNeg x y  = negate $ fst $ dividedBy (abs x) (abs y)

-- The old implementation of dividedBy, which works only for positive inputs.
dividedBy :: Integral a => a -> a -> (a, a)
dividedBy num denom =
  go num denom 0
  where
    go n d count
      | n < d = (count, n)
      | otherwise = go (n - d) d (count + 1)

…and a test suite…

import Test.Hspec (hspec, context, describe, it, shouldBe)
import Lib (dividedBy', DividedResult(..))

-- The main issue we want to address is that
-- dividedBy doesn't handle divisors of 0 or
-- less.
main :: IO ()
main = hspec $ do
  describe "dividedBy'" $ do
    it "10 2 -> Result 5" $ do
      dividedBy' 10 2 `shouldBe` Result 5
    it "10 (-2) -> Result (-5)" $ do
      dividedBy' 10 (-2) `shouldBe` Result (-5)
    it "(-10) (-2) -> Result 5" $ do
      dividedBy' (-10) (-2) `shouldBe` Result 5
    it "(-10) 2 -> Result (-5)" $ do
      dividedBy' (-10) 2 `shouldBe` Result (-5)
    it "8 0 -> DividedByZero" $ do
      dividedBy' 8 0 `shouldBe` DividedByZero
    it "0 8 -> 0" $ do
      dividedBy' 0 8 `shouldBe` Result 0

Navigate to exercises/8.6.4_-_fixing_dividedby.rst.d/dividedby and run stack test to execute the test suite.

8.6.5 McCarthy 91 function

The McCarthy 91 function yields \(x - 10\) when \(x > 100\) and \(91\) otherwise.

Name your function mc91. When you run map mc91 [95..110] you should get [91,91,91,91,91,91,91,92,93,94,95,96,97,98,99,100] in return.

Here is the main logic.

module Lib where

mc91 n
  | n > 100  = n - 10
  | n <= 100 = mc91 (mc91 (n+11))

…and here that single test, so you don’t have to type it in GHCi:

module Main where
import Test.Hspec
import Lib

main = hspec $ do
  describe "mc91" $ do
    it "should work for the example input" $ do
      map mc91 [95..110] `shouldBe` [91,91,91,91,91,91,91,92,93,94,95,96,97,98,99,100]
    it "should return 91 where n > 1 && n <= 100"$ do
      map mc91 [1..100] `shouldBe` take 100 (cycle [91])