Call another function only once in a recursive function in Haskell-CodePudding

In Haskell, I have defined a recursive function. In this recursive function, I need to access the elements of a list.

This list is a list with different integers, which is created by another function. If I specify where lst = func_that_creates_list in this recursive function, the list gets created every time, which is very time consuming.

So somehow, I need to call this function that created this list only once and then use this list throughout the recursive function, but I don't now how to do this. Can anyone help me?

makeList :: Int -> [Integer]
makeList n = map (^2) [0..n]

recFunc :: Int -> [Integer]
recFunc 0 = 1
recFunc n = recFunc (n-1)   2 * x!!n where n = makeList n

CodePudding user response：

That's one instance of the common go-function idiom.

recFunc :: Int -> [Integer]
recFunc n = go n
 where go 0 = 1
       go n' = recFunc (n'-1)   2 * x!!n'
       x = makeList n

But as it is, this actually won't improve performance much because you're using the evil !! operator. Direct-indexing into a precomputed list is basically just as bad a computing it from scratch. Different story with vectors, but there's really no reason to use direct access here.

The proper way is to deconstruct the list as you go:

recFunc n = go n . reverse $ makeList n
 where go n' (xω:x) = recFunc (n'-1) x   2 * xω
       go _ _ = 1

Actually the n' argument is unnecessary now

recFunc = go . reverse . makeList
 where go (xω:x) = recFunc x   2 * xω
       go [] = 1

Still not optimal because you're carrying around a buildup of lazy thunks, better with a strict accumulator, that also makes the reverse unnecessary. (Well, it's anyway unnecessary in this example...)

recFunc = go 1 . makeList
 where go acc (x₀:x) = acc `seq` go (2*x₀ acc) x
       go acc [] = acc

But this function pattern is already implemented as foldl':

import Data.List

recFunc = foldl' (\acc x -> 2*x   acc) 1 . makeList

or simply

recFunc = (1 ) . sum . map (2*) . makeList

Then you might of course also just inline makeList and fuse the map:

recFunc n = 1   sum ((2*) . (^2) <$> [0..n])

CodePudding user response：

You have a typo in the definition. Corrected, it is

makeList :: Int -> [Integer]
makeList n = map (^2) [0..n]

recFunc :: Int -> [Integer]
recFunc 0 = 1
recFunc n = recFunc (n-1)   2 * xs!!n
                         where  xs = makeList n

We can expand few more basic cases, taking care to rename variables so that all names are unique:

recFunc 0 = 1
recFunc 1 = recFunc 0   2 * xs1!!1
                         where  xs1 = makeList 1
          = 1   2 * xs1!!1
                         where  xs1 = makeList 1
recFunc 2 = recFunc 1   2 * xs2!!2
                         where  xs2 = makeList 2
          = 1   2 * xs1!!1   2 * xs2!!2
                         where  xs1 = makeList 1
                                xs2 = makeList 2
recFunc 3 = recFunc 2   2 * xs3!!3
                         where  xs3 = makeList 3
          = 1   2 * xs1!!1   2 * xs2!!2   2 * xs3!!3
                         where  xs1 = makeList 1
                                xs2 = makeList 2
                                xs3 = makeList 3
-- ....

Indeed we see the problem you've indicated. But if we think about it for a moment, all the generated lists are the prefixes of the same list:

    xs1 !! 1  ==  xs2 !! 1  ==  xs3 !! 1  ==  ....

and so we can re-write the above as

recFunc 0 = 1
recFunc 1 = 1   2 * xs3!!1
                         where  xs3 = makeList 3
recFunc 2 = 1   2 * xs3!!1   2 * xs3!!2
                         where  xs3 = makeList 3
recFunc 3 = 1   2 * xs3!!1   2 * xs3!!2   2 * xs3!!3
                         where  xs3 = makeList 3
-- ....

and suddenly the problem goes away:

recFunc n = 1   sum [ 2*xs!!i | i <- [1..n] ]
                         where  xs = makeList n

Repeatedly scanning the list to sequential indices is a quadratic calculation, but the end result is we just access the list's elements in sequence, starting from the 2nd element in the list:

recFunc n = 1   sum [ 2*x   | x <- tail xs]
                         where  xs = makeList n
          = 1   sum [ 2*x   | x <- tail $ map (^2) [0..n]]
          = 1   sum [ 2*x   | x <-        map (^2) [1..n]]
          = 1   sum [ 2*x^2 | x <- [1..n]]

or, iteratively,

recFuncList = scanl ( ) 1 . map (2*) . 
                scanl ( ) 1 . iterate ( 2) $ 3

  = scanl (\acc x -> acc   2*x) 1 . 
       scanl (\acc x -> acc   x) 1 . iterate ( 2) $ 3

--      3  5  7  9  11  13  15  17  19  21  ...
--    1  4  9  16  25  36  49  64  81  100  121  ...
--  1  3  11 29  61 111 183 281 409  571  771  1013  ...

  = scanl ( ) 1 . scanl ( ) 2 . iterate ( 4) $ 6

whichever you prefer.