0

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

1
  • I would get rid of !!. This operator is linear in Haskell. If you need constant access time use Data.Array. Commented Oct 10, 2021 at 22:34

2 Answers 2

2

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])
Sign up to request clarification or add additional context in comments.

Comments

0

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.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.