Map functions basics in Haskell

Question

I'm self learning Haskell and have come across an issue with the map function and was looking for help. What i'm trying to do is take a list of lists and if a list is empty so is [] and one of the other lists has a 1 in the head. Then to take that 1 and put it in the [] list.

a = [[2,1,3,1],[],[2,3],[1,2,3],[4]]

and make it

a = [[2,1,3,1],[1],[2,3],[2,3],[4]]

so far I have something along the lines of I haven't got the complete thing.

((map (\k-> if ([])&&(elem 1 heads))a) 
where heads = map head a

But I also have to have it so that if a = [[1,2,1,3,1],[],[2,3],[1,2,3],[4]] will give a = [[2,1,3,1],[1],[2,3],[1,2,3],[4]] so it only moves one 1 to the empty list.

I know this wont work, but I have been trying to do it for a couple of hours now but i'm not getting anywhere

Answer 1

IMO map isn't really the right function for this job. Conceptually map transforms each element of a collection using a function that only looks at the element itself. Obviously you can write a map where the function uses "external" variables using lambdas, scoping etc. but I suggest staying as close to the concept of map as possible.

The idea of "take that 1 and put it in the [] list." implies (take and put) an imperative approach with side-effects, something we want to avoid as much as possible in a purely functional language as haskell.

You can think about it in another way: there is no need to actually "move" the 1, i.e. to know which 1 ends up in which []. Counting the number of empty lists (let's call it x) and the number of lists that start with 1 (y) is enough, we just have then to create a new lists that

• replaces the first min(x,y) occurrences of empty lists with [1]
• Takes the tail of the first min(x,y) lists that start with 1

A probably improvable implementation:

redistributeOnes :: [[Int]] -> [[Int]]
redistributeOnes xs = redistributeOnes' n n xs where
  n = min (length $ filter (==[]) xs) (length $ filter (\l -> if l == [] then False else (head l) == 1) xs)
  redistributeOnes' _ _ [] = []
  redistributeOnes' 0 0 xs = xs
  redistributeOnes' n m ([]:xs) | n > 0 = [1] : redistributeOnes' (n-1) m xs
                                | otherwise = [] : redistributeOnes' n m xs
  redistributeOnes' n m (x:xs)  | head x == 1 && m > 0 = (tail x) : redistributeOnes' n (m-1) xs
                                | otherwise = x : redistributeOnes' n m xs

Tests:

λ> redistributeOnes [[], [1,2]]
[[1],[2]]
λ> redistributeOnes [[], [1,2], [], [], [1,2,3]]
[[1],[2],[1],[],[2,3]]
λ> redistributeOnes [[], [1,2], [], [1,2,3]]
[[1],[2],[1],[2,3]]
λ> redistributeOnes [[]]
[[]]
λ> redistributeOnes [[], [1,2,3]]
[[1],[2,3]]
λ> redistributeOnes [[1,2,3]]
[[1,2,3]]
λ> redistributeOnes [[1,2,3], [], [], [], [2,5,1], [1,2], [], [1,100]]
[[2,3],[1],[1],[1],[2,5,1],[2],[],[100]]

Answer 2

The problem is straightforward if approached from the right direction. As a first approximation, you can define your function as a left fold over the input list:

fun :: Eq a => a -> [[a]] -> [[a]]
fun z xss = newList 
  where (foundZ, newList, _) = foldl ... (False, [], False) xss

Note that the fold will return two values, namely the resulting list and a boolean indicating if a 1 (or in this case, the parameter z) is found in the list. The third parameter indicates if a list has already been replaced (we only want to do one replacement). If we are clever (and we will be) we can use the value of foundZ inside the body of the function passed to foldl - that is, we can use it before it has apparently been computed. All that is left is to write the argument function to foldl:

\(fn,xss',rpl) xs ->
  case xs of 
    ...

Consider the different possibilities for xs: it is the empty list, it is the list containing a z as its head, and every other list:

    [] | not rpl -> ...
    (x:r) | x == z && not fn -> ...
    _  -> (fn, xs:xss',rpl)

Note that when we check for x == z we also check not fn because we only want to take a single z from a single list, so if we already found one, we do not want to do that again. In the case for the empty list, we check for not rpl for the same reason. The last case is obvious, but the first two may not be.

    [] | not rpl -> (fn, (if foundZ then [z] else []):xss', True)

The case for the empty list simple checks if the z was found - if so, it returns a singleton list containing that z.

    (x:r) | x == z && not fn -> (True , r:xss', rpl) 

The case for the list starting with a z returns True for found and prepends the tail of that list to the result (this is how the 1 gets removed).

Put it all together and you get a simple function:

fun :: Eq a => a -> [[a]] -> [[a]]
fun z xss = reverse newList 
  where (foundZ, newList, _) = 
          foldl 
            (\(fn,xss',rpl) xs ->
              case xs of 
                [] | not rpl -> (fn, (if foundZ then [z] else []):xss', True)
                (x:r) | x == z && not fn -> (True , r:xss', rpl) 
                _  -> (fn, xs:xss', rpl)
            ) (False, [], False) xss 

and

>fun 1 [[2,1,3,1],[],[2,3],[1,2,3],[4]]
[[2,1,3,1],[1],[2,3],[2,3],[4]]
>fun 1 [[1,2,1,3,1],[],[2,3],[1,2,3],[4]]
[[2,1,3,1],[1],[2,3],[1,2,3],[4]]

Answer 3

Here I attempted to write easy-to-understand functional solution for a beginner. This can be implemented more efficiently, of course.

doStuff :: Integral a => [[a]] -> [[a]]
doStuff xs = let n = min holes donors in go n n xs
  where go _ _ []          = []
        go 0 m ([]:ys)     = []     : go 0       m ys
        go n m ([]:ys)     = [1]    : go (n - 1) m ys
        go n 0 ((1:zs):ys) = (1:zs) : go n       0 ys
        go n m ((1:zs):ys) = zs     : go n (m - 1) ys
        go n m (y:ys)      = y      : go n m       ys
        holes              = count null    xs
        donors             = count goodish xs
        count f            = length . filter f
        goodish (1:_)      = True
        goodish _          = False

It even works:

λ> doStuff [[2,1,3,1],[],[2,3],[1,2,3],[4]]
[[2,1,3,1],[1],[2,3],[2,3],[4]]
λ> doStuff [[1,2,1,3,1],[],[2,3],[1,2,3],[4]]
[[2,1,3,1],[1],[2,3],[1,2,3],[4]]
λ> doStuff [[1,2,1,3,1],[],[2,3],[1,2,3],[4],[],[]]
[[2,1,3,1],[1],[2,3],[2,3],[4],[1],[]]

Answer 4

This looks like it's going to be a horribly fussy problem to solve in an incremental fashion. Therefore, I suggest you think about monolithic solutions. Start off by counting the total number of empty lists and the total number of lists that start with 1. Armed with these results, attack the original input again. The counting is easily done using foldl' if you're familiar with that, or you could use explicit recursion, or if you don't care about efficiency you could filter and count twice; the final attack will be easiest using explicit recursion.