CODEWITHSUNDEEP
haskelltail-recursion
Aistis Taraskevicius
Aistis Taraskevicius

Reputation: 811

Haskell tail recusion for multi call function

Here is non tail recursive function

alg :: Int -> Int
alg n = if n<7 then n else alg(n-1) * alg(n-2) * alg(n-4) * alg(n-6)

I've been stuck on this for a while, I get the basic idea of tail recursion, and how to do it for single call recursive function, but no clue how to do it for multi call one.

Even came up with this abomination 

algT :: Int -> Int
algT n = tail1 n 0 where tail1 i r = tail1(i-1) r *
         tail2 n 0 where tail2 i r = tail2(i-2) r *
         tail3 n 0 where tail3 i r = tail3(i-4) r *
         tail4 n 0 where tail4 i r = tail4(i-6) r

It doesnt work and obviously not how recursive function should look, had few other attempts, but all of them ended in infinite 100% cpu load loop...

Upvotes: 2

Views: 202

Answers (4)

Guvante
Guvante

Reputation: 19221

Have you looked into Fibonacci in Haskell? It is a similar type of function. BTW tail recursion isn't quite the right term in Haskell, as multi-recursion functions can't really be done recursively but Haskell's lazy nature makes a similar but more powerful trick possible. Here is the standard one given:

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

Using the same trick on yours gives EDIT: As a function

alg :: Int -> Int
alg n = alg' !! (n - 1)
    where alg' = 1 : 2 : 3 : 4 : 5 : 6 : zipWith4 (\a b c d -> a * b * c * d) (drop 5 alg') (drop 4 alg') (drop 2 alg') alg'

Note that you shouldn't use Int here, that isn't open ended and the 11th term will loop in an Int.

EDIT: Actually Int is even worse than I thought. Once you hit 32 2's in your result you will start returning 0 since every answer is 0 mod 2^32.

Upvotes: 3

rafalio
rafalio

Reputation: 3946

Here is a possible solution.

let f = [1..6] ++ foldr1 (zipWith (*)) [f, drop 2 f, drop 4 f, drop 5 f]

or even:

let f = [1..6] ++ foldr1 (zipWith (*)) (map (flip drop $ f) [0,2,4,5])

Upvotes: 0

user2512323
user2512323

Reputation:

From your question it's not entirely clear what is the purpose of making your function tail-recusrive. If you are trying to reduce cpu/memory usage, then you should use memoization (mentioned in the Guvante's answer).

Meanwhile, there is a way to make almost any function tail-recursive, known as continuation-passing style. Your example written in the CPS looks like this:

alg_cps :: Integer -> (Integer->a) -> a
alg_cps n cont = 
    if n < 7 
    then cont n 
    else alg_cps (n - 1) 
        (\x1 -> alg_cps (n - 2) 
            (\x2 -> alg_cps (n - 4) 
                (\x3 -> alg_cps (n - 6)
                    (\x4 -> cont (x1*x2*x3*x4)))))

And to directly get the result you can call it with id as continuation:

alg_cps 20 id

Notice that this does not reduce algorithm complexity or memory usage compared to naive non-tail recursive implementation.

Upvotes: 2

genisage
genisage

Reputation: 1169

I think I have a solution, but it's not very elegant or pretty.

alg :: Int -> Int
alg n | n < 7     -> n
      | otherwise -> alg' n (repeat 0)

alg' :: Int -> [Int] -> Int
alg' n [] = error "something has gone horribly wrong"
alg' n l@(x:y)
  | n < 5     -> error "something else has gone horribly wrong"
  | n == 6    -> product $ zipWith (^) [6,5..1] l
  | otherwise -> alg' (n-1) $ zipWith (+) [x,x,0,x,0,x] (y ++ [0])

The idea is that you can keep track of how many times you're supposed to be multiplying each thing without actually doing any of the calculations until the very end. At any given time, you have information about how many times you've needed any of the next 6 values, and once you're below 7, you just raise 1-6 to the proper powers and take their product.

(I haven't actually tested this, but it seems right. And even if it's not I'm pretty sure the idea behind it is sound)

P.S. As @Guvante says, Int isn't a good choice here as it will quickly overflow. As a general rule I use Integer by default and only switch if I have a good reason.

Upvotes: 0

Related Questions