Haskell: Increment elements of a list by cumulative length of previous lists-CodePudding

Here is the list of lists: [[1,2,3],[1,2,3,4],[1,2,3]]

How can I increment each element of the second list by the length of the first list, and increment the third list by the length of the first list second list? The first list should remain unchanged.

Intended output: [[1,2,3],[4,5,6,7],[8,9,10]]

Since the first list has length 3, the second list is generated by [1 3, 2 3, 3 3, 4 3].

Since the first list second list combined have length 7, the third list is generated by [1 7, 2 7, 3 7].

Ideally it should work with any number of lists.

So far, I've had slight sucess using this:

scanl1 (\xs ys -> [y length xs | y <- ys]) [[1,2,3],[1,2,3,4],[1,2,3]]

which outputs: [[1,2,3],[4,5,6,7],[5,6,7]]

CodePudding user response：

scanl1 is a good idea, but it's not quite right, because you don't want your accumulator to be a list, but rather to be an integer. So you really want scanl, not scanl1. I'll leave it as an exercise for you to see how to adjust your solution - given that you managed to write something almost-right with scanl1, I don't think you'll find it too hard once you have the right function.

In the comments, jpmariner suggests mapAccumL :: (s -> a -> (s, b)) -> s -> [a] -> (s, [b])). That's perfectly typed for what we want to do, so let's see how it would look.

import Data.Traversable (mapAccumL)

addPreviousLengths :: [[Int]] -> [[Int]]
addPreviousLengths = snd . mapAccumL go 0
  where go n xs = (n   length xs, map (  n) xs)

λ> addPreviousLengths [[1,2,3],[1,2,3,4],[1,2,3]]
[[1,2,3],[4,5,6,7],[8,9,10]]

mapAccumL really is the best tool for this job - there's not much unnecessary complexity involved in using it. But if you're trying to implement this from scratch, you might try the recursive approach Francis King suggested. I'd suggest a lazy algorithm instead of the tail-recursive algorithm, though:

incrLength :: [[Int]] -> [[Int]]
incrLength = go 0
  where go _ [] = []
        go amount (x:xs) =
          map (  amount) x : go (amount   length x) xs

It works the same as the mapAccumL version. Note that both versions are lazy: they consume only as much of the input list as necessary. This is an advantage not shared by a tail-recursive approach.

λ> take 3 . incrLength $ repeat [1]
[[1],[2],[3]]
λ> take 3 . addPreviousLengths $ repeat [1]
[[1],[2],[3]]

CodePudding user response：

There are many ways to solve this. A simple recursion is one approach:

lst :: [[Int]]
lst = [[1,2,3],[1,2,3,4],[1,2,3]]

incrLength :: [[Int]] -> Int -> [[Int]] -> [[Int]]
incrLength [] _ result = result
incrLength (x:xs) amount result =
   incrLength xs (amount   length x) (result    [map ( amount) x])

(Edit: it is more efficient to use (:) in this function. See @amalloy comment below. The result then has to be reversed.

incrLength :: [[Int]] -> Int -> [[Int]] -> [[Int]]
incrLength [] _ result = reverse result
incrLength (x:xs) amount result =
   incrLength xs (amount   length x) (map ( amount) x : result)

End Edit)

Another approach is to use scanl. We use length to get the length of the inner lists, then accumulate using scanl.

 map length lst                      -- [3,4,3]
 scanl ( ) 0 $ map length lst        -- [0,3,7,10]
 init $ scanl ( ) 0 $ map length lst -- [0,3,7]

Then we zip the lst and the accumulated value together, and map one over the other.

 incrLength' :: [[Int]] -> [[Int]]
 incrLength' lst = 
      [map (  snd y) (fst y) | y <- zip lst addlst]
    where 
       addlst =init $scanl ( ) 0 $ map length lst 

main = do
    print $ incrLength lst 0 []    -- [[1,2,3],[4,5,6,7],[8,9,10]]