4

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

Improve this question
6
  • And if there aren't any other lists with 1 in the head? Leave the empty list empty? Commented Dec 10, 2015 at 16:05
  • Yeah, sorry forgot to mention that. Just realised I need an then and else Commented Dec 10, 2015 at 16:06
  • When searching for a list that starts with 1, do you want to check only lists after the current empty list or they may be wherever in the list of lists, even before the current empty list? Commented Dec 10, 2015 at 16:10
  • 1
    all the heads of the lists. So the it could be a = [[1,3,1],[],[2,3],[9,1,2,3],[4]] and would give a = [[3,1],[1],[2,3],[9,1,2,3],[4]] Commented Dec 10, 2015 at 16:16
  • 3
    map might not be the best approach here since you're not uniformly applying a function to all elements. Perhaps, an explicit recursion fits better. Also, I think you want to have these two actions happen both or none at all. So the number of total numbers stay invariant. Commented Dec 10, 2015 at 16:36

4 Answers 4

Reset to default
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],[]]
Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

1

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]]
Improve this answer

6 Comments

I'm getting an indentation or brackets mismatched error on the foldl. but this look like a great solution
The code compiles - perhaps you have not copied a parentheses or changed the indentation by mistake.
I think whe i copied it the indentations got moved
Quick question, whats fn?
It is the parameter bound in the function (\(fn,xss') xs -> ...), and it indicates whether or not z has been found in the list seen so far.
|
1

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.

Improve this answer

1 Comment

Ok, whats the best way to use foldl?
0

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]]
Improve this answer

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.