Using Accumulators in chapter 4

Help
#1

There is this exercise from purescript book to make a tail recursive function which outputs a fibonacci sequence.

I wrote this as the function currently

--fibTailRec :: forall a. Int a -> Int
fibTailRec n = fib' n 0
  where
--    fib' :: Int -> Int ?
    fib' n' acc =
      if null n'
        then acc
      else fib' n' (acc - 1) + (acc - 2)
--      fib (n - 1) + fib (n - 2) - for reference only

But it gives me this error

$ spago test
Compiling Test.Main
Warning 1 of 5:

  in module Test.Main
  at test/Main.purs:7:1 - 7:30 (line 7, column 1 - line 7, column 30)

    The import of Data.Maybe is redundant


  See https://github.com/purescript/documentation/blob/master/errors/UnusedImport.md for more information,
  or to contribute content related to this warning.

Warning 2 of 5:

  in module Test.Main
  at test/Main.purs:9:1 - 9:24 (line 9, column 1 - line 9, column 24)

    The import of Data.Tuple is redundant


  See https://github.com/purescript/documentation/blob/master/errors/UnusedImport.md for more information,
  or to contribute content related to this warning.

Warning 3 of 5:

  in module Test.Main
  at test/Main.purs:3:1 - 3:15 (line 3, column 1 - line 3, column 15)

    Module Prelude has unspecified imports, consider using the explicit form:

      import Prelude (class Eq, class Ord, class Show, Unit, discard, negate, ($), (<$>), (==))                                                                             



  See https://github.com/purescript/documentation/blob/master/errors/ImplicitImport.md for more information,
  or to contribute content related to this warning.

Warning 4 of 5:

  in module Test.Main
  at test/Main.purs:4:1 - 4:21 (line 4, column 1 - line 4, column 21)

    Module Test.Examples has unspecified imports, consider using the explicit form:

      import Test.Examples (allFiles, allFiles', fact, factTailRec, factors, factorsV2, factorsV3, fib, length, lengthTailRec)                                              



  See https://github.com/purescript/documentation/blob/master/errors/ImplicitImport.md for more information,
  or to contribute content related to this warning.

Warning 5 of 5:

  in module Test.Main
  at test/Main.purs:5:1 - 5:24 (line 5, column 1 - line 5, column 24)

    Module Test.MySolutions has unspecified imports, consider using the explicit form:

      import Test.MySolutions (allTrue, cartesianProduct, countEven, fibTailRec, isEven, isPrime, keepNonNegative, keepNonNegativeRewrite, squared, (<$?>))                 



  See https://github.com/purescript/documentation/blob/master/errors/ImplicitImport.md for more information,
  or to contribute content related to this warning.


Error found:
in module Test.Main
at test/Main.purs:126:26 - 126:27 (line 126, column 26 - line 126, column 27)

  Could not match type
       
    Int
       
  with type
            
    Array t0
            

while checking that type Int
  is at least as general as type Array t0
while checking that expression 0
  has type Array t0
in value declaration main

where t0 is an unknown type

See https://github.com/purescript/documentation/blob/master/errors/TypesDoNotUnify.md for more information,
or to contribute content related to this error.


[error] Failed to build.

What is actually meant with executing things in the back?

#2 
null
function is designed to test the emptiness of an Array. Instead, you could simply test if 
n'== 0
or use pattern matching.

As for all the warnings, you can remove all the redondant ones from your imports.

1 Like
#3

Also note that the function is not actually tail-recursive. I think that instead of

fib' n' (acc - 1) + (acc - 2)

you probably meant

fib' n' $ (acc - 1) + (acc - 2)

The earlier code executes fib' with the arguments n' and acc - 1 and then adds the result to acc - 2, which I’m pretty sure is not what you want. In the latter code, fib' is executed with n' and (acc - 1) + (acc - 2) as its arguments.

Even then, the code is still incorrect. You’re not changing n''s value anywhere, so the n == 0 condition will never be satisfied, and fib' will recurse forever. You’ll have to modify n' in the else branch, but I don’t want to fully spoil the answer.

2 Likes
#4

I still don’t get what the acc specificly does other than temporarily storing a variable for iteration.

I changed the line to this

  else fib' n' $ (acc - 1) + (acc - 2) (n'-acc)

it gave me this error instead

Error found:
in module Test.MySolutions
at test/MySolutions.purs:111:34 - 111:52 (line 111, column 34 - line 111, column 52)

  Could not match type
       
    Int
       
  with type
             
    Int -> t0
             

while applying a function ((sub (#dict Ring t54)) acc) 2
  of type Int
  to argument (sub n') acc
while checking that expression ((sub acc) 2) ((sub n') acc)
  has type Int
in value declaration fibTailRec

where t0 is an unknown type

See https://github.com/purescript/documentation/blob/master/errors/TypesDoNotUnify.md for more information,
or to contribute content related to this error.


[error] Failed to build.

shouldn’t something from n’ be removed, as from the acc variable?

#5

Did remove an error using that, thanks.

But pattern maching seems to be the naxt chapter in purescript book, so I didn’t have that yet. Is pattern matching together with tail recursion often used?

#6

I’ll parenthesize this so the mistake will be more obvious:

else fib' n' $ ((acc - 1) + ((acc - 2) (n'-acc)))

Yes, you’re right, but you’re not removing the correct value. Here’s another hint:

else fib' ({- here's where you "modify" n -}) $ (acc - 1) + (acc - 2)

Think about it: as you go deeper into the fib's call stack, what should happen to n? Should it increase, or decrease? If so, by how much?

Also, you’re not actually modifying acc in the correct way. Again, I don’t want to spoil the correct answer.

#7

Pattern matching and tail recursion are both often used, but for different reasons. Pattern matching is preferred for concision, I guess, whereas tail recursion is known for efficiency.