CODEWITHSUNDEEP
haskellrecursion
Softey
Softey

Reputation: 1491

Haskell recursive function add to the end of a list

I have a recursive Haskell function that takes a number n and generates a list that is n long of squared numbers from 1 up.

The code works but instead of the list for n=3 being [9,4,1] I want it to be [1,4,9].

sqNList :: Int -> [Int]
sqNList 0  = []
sqNList n  = n*n : sqNList (n-1)

I've tried swappig the : for a ++ but then the pattern matching doesn't work. I have only just started Haskell today so may be obvious

Upvotes: 1

Views: 3737

Answers (3)

chepner
chepner

Reputation: 532208

This is a more advanced technique, so you may want to just save this for future study.

Most recursive functions tend to use one of the same general forms of recursion, so knowing which higher-order function to use saves you the effort of reimplementing (possibly incorrectly) the recursion, and lets you focus on the work that is unique to your problem.

This particular type of recursion is captured by the unfoldr function, defined in Data.List, which lets you generate a (possibly infinite) list using a generator function and an initial seed value.

Its definition can be as simple as

unfoldr f x = case f x of
                    Nothing -> []
                    Just (new, next) = new : unfoldr f next

although the actual definition is slightly more complicated for efficiency.

Essentially, you just call the generator f on the seed value x. If the result is Nothing, return an empty list. Otherwise, build a list containing a result and the list produced by a recursive call with a new seed value.

Applying this to your problem, we produce a square and the next integer as long as the input is still small enough.

import Data.List (unfoldr)
sqNList n = unfoldr generator 1
            where generator x = if x > n then Nothing else Just (x*x, x+1)

So for a simple example like sqNList 3, it proceeds as follows:

  1. Call generator 1 and get back Just (1, 2); the accumulator is now [1].
  2. Call generator 2 and get back Just (4, 3); the accumulator is now [1,4].
  3. Call generator 3 and get back Just (9, 4); the accumulator is now [1,4,9].
  4. Call generator 4 and get back Nothing. Return the accumulator [1,4,9] as the result.

Note that you generate the infinite list of all squares simply by never returning Nothing:

allSquares = unfoldr (\x -> Just (x*x, x+1)) 1

Haskell, being lazy, only generates elements in the list as you need them, so you could also define sqNList by taking only the first n items of the infinite list.

sqNList n = take n (unfoldr (\x -> Just (x*x, x+1)) 1)

Upvotes: 4

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 477608

The easiest approach that consumes probably the least amount of memory is to work with an accumulator: a parameter you pass and update through every recursive call.

Right now you use n as an accumulator, and decrement that, but we can decide to use an accumulator i instead that starts at 1, and keeps incrementing:

helper :: Int -> Int -> [Int]
helper i n | i > n = []
           | otherwise = i*i : helper (i+1) n

Now we of course have to call it with i = 1 ourselves, which is not ideal, but we can use a where clause that scopes the helper in the sqNList:

sqNList :: Int -> [Int]
sqNList n = helper 1 n
    where helper :: Int -> Int -> [Int]
          helper i n | i > n = []
                     | otherwise = i*i : helper (i+1) n

Now we can improve this a bit. For instanc there is no need to pass n through the helper calls, since it does not change, and is defined at the top level:

sqNList :: Int -> [Int]
sqNList n = helper 1
    where helper :: Int -> [Int]
          helper i | i > n = []
                   | otherwise = i*i : helper (i+1)

There is furthermore no need to only work with Ints: we can use any type a for which Num a and Ord a:

sqNList :: (Num a, Ord a) => a -> [a]
sqNList n = helper 1
    where helper i | i > n = []
                   | otherwise = i*i : helper (i+1)

Upvotes: 6

Carl
Carl

Reputation: 27023

The best approach is to implement sqNList in terms of a helper function that counts from 1 up to n. That way you can just generate the list in the correct order in the first place.

sqNList :: Int -> [Int]
sqNList n = sqNListHelper 1 n

sqNListHelper :: Int -> Int -> [Int]
sqNListHelper current end = ...

There are a wide variety of more sophisticated approaches, but this is the easiest approach to debug/test interactively that also has you figuring out how to do everything yourself.

More sophisticated approaches can include list comprehensions or composing functions like map and enumFromTo to build up the logic from simpler pieces.

Upvotes: 6

Related Questions