CODEWITHSUNDEEP
haskellrecursion
Sven Koschnicke
Sven Koschnicke

Reputation: 6711

Remove explicit recursion from function with dependent values

I have the following Haskell function which uses explicit recursion:

f :: [a] -> [a]
f (a:b:xs) = g a b : f (g a b : xs)
  where
    g :: a -> a -> a
f (_:[])   = []
f []       = []

Note that the recursive call depends on the value calculated in the step before (by g).

Is there a way to remove the explicit recursion and if so, how?

Upvotes: 3

Views: 165

Answers (2)

Emil Vikström
Emil Vikström

Reputation: 91963

Your function is exactly a fold that emits intermediate values. In Haskell this is called a scan. Specifically, scanl1 is equivalent to your f except the first element.

f = drop 1 . scanl1 g

Upvotes: 12

user3177338
user3177338

Reputation: 99

use tail recursion, ghc can optimaze it

f (a:b:xs) acc = f (g a b : xs) (g a b : acc)
f _ acc = reverse acc

and call so

f myList []

Upvotes: -3

Related Questions