Indexed list of lists in haskell-CodePudding

I am looking for a way to merge a list of lists with a singular list, that keeps the structure of the list of lists. I.e. a function foo that works like this:

foo :: [[a]] -> [b] -> [[(a,b)]]

> foo [[1],[2,2,3],[7,8]] [0..]
[[(1,0)],[(2,1),(2,2),(3,3)],[(7,4),(8,5)]]

(Or the other way around with the arguments)

foo :: [b] -> [[a]] -> [[(b,a)]]

> foo [0..] [[1],[2,2,3],[7,8]]
[[(0,1)],[(1,2),(2,2),(3,3)],[(4,7),(5,8)]]

Of course, if we know that each list is equal in length, this function could easily be created by:

import Data.List.Split (chunksOf)

foo :: [[a]] -> [b] -> [[(a,b)]]
foo xs ys = chunksOf n $ zip (concat xs) ys
  where
    n = length $ head xs

But how can this function be done in the more general case of unequal list lengths?

CodePudding user response：

You can use a nested traversal: traverse the outer list, traversing each inner list, and at each step popping off an element of the other list and pairing it with the currently traversed element. This can be written nicely in the state monad:

import Control.Monad.Trans.State

foo :: ∀ a b . [[a]] -> [b] -> [[(a,b)]]
foo ls ys = evalState nestedTrav ys
 where nestedTrav :: State [b] [[(a,b)]]
       nestedTrav = forM ls $ \l ->
                      forM l $ \x ->
                        state $ \(y:ys) -> (ys, (x,y))

... or shorter

foo ls ys = (`evalState`ys)
            . forM ls . traverse
            $ \x -> state $ \(y:ys) -> (ys, (x,y))

This only works if the second list is as least as long as all first lists together (or infinite, as in your example). I suggest you implement the general case by dissecting the traversal version into folds and/or recursion, and then adding an abort mechanism when the second list has gone empty.

CodePudding user response：

You can work with the traversal mechanism as explained by @leftaroundabout. This can easily be generalized to work with all sorts of Traversables.

A simple function that will only work for lists of lists, is by working with a helper function:

foo :: [b] -> [[a]] -> [[(b,a)]]
foo _ [] = []
foo ts (xs:xss) = let ~(ts', xs') = _helper ts xs in xs' : foo ts' xss
    where _helper [] _ = ([], [])
          _helper as [] = (as, [])
          _helper (a:as) (b:bs) = let ~(as', bs') = _helper as bs in (as', (a, b): bs')

Here the _helper function will return a 2-tuple of the list of remaining "tags" and the list of tagged objects. We thus call _helper for each sublist and keep track of the remaining tags to dispatch to the next sublist.