CODEWITHSUNDEEP
haskell
user1887556
user1887556

Reputation: 27

Haskell search an element on a List

I want a function that changes (1 to 0) on a list of lists, when number of 1's in that line/column isn't even. I have done these functions:

1) Sees if the lines in a list are even or not:

  parityLine :: [[Int]] -> [Bool]
  parityLine [] =[]
  parityLine (x:xs)
                |sum(x) `mod` 2 == 0 = True:(parityLine(xs))
                |otherwise = False:(parityLine(xs))

2) Sum the corresponding elements on a list of lists:

 sumPositions :: [[Int]] -> [Int]
 sumPositions [] = []
 sumPositions (x:xs) = foldl (zipWith (+)) (repeat 0) (x:xs)

3) Sees if the columns in a list are even or not:

 parityColumn :: [Int] -> [Bool]
 parityColumn [] = []
 parityColumn (x:xs)
    |head(x:xs) `mod` 2 == 0 = True:parityColumn(xs)
    |otherwise = False:parityColumn(xs)

4) Does the operation or with two boolean lists:

 bol :: [Bool] -> [Bool] -> [[Bool]]
 bol  [] _ = []
 bol (x:xs) (y:ys)= (map (||x) (y:ys)):(bol xs (y:ys))

5) Correct List:

 correct :: [[Int]] -> [[Bool]]
 correct [] = []
 correct (x:xs)=(bol(parityLine (x:xs))(parityColumn(sumPositions(x:xs))))

So what I want is to alter the function correct to [[Int]]->[[Int]] that does this:

    My Int list(x:xs)                 With my correct function applied

    [[0,0,1,1],                            [[True,True,True,True],
     [1,0,1,1],                             [True,True,False,True],
     [0,1,0,1],                             [True,True,True,True]
     [1,1,1,1]]                             [True,True,True,True]]

Now I can see that in the second line third column, False, so I have to correct that number 1 to have a number of 1's even. If there is more than one False in that list, I only want to correct one of these 1's.

As a result, I want that function correct returns:

 [[0,0,1,1],
  [1,0,0,1],
  [0,1,0,1],
  [1,1,1,1]]

Thanks.

Upvotes: 1

Views: 2259

Answers (2)

AndrewC
AndrewC

Reputation: 32455

I'll give an answer that starts where you are rather than from scratch, so we're doing it more your way than mine.

First let's do it for a single element:

leaveIf :: Bool -> Int -> Int
leaveIf yes 0 = if yes then 0 else 1
leaveIf yes 1 = if yes then 1 else 0

(You could use guards for that, but my phone doesn't have the vertical bar character!)

Next we can do it for a list of lists:

edit :: [[Bool]] -> [[Int]] -> [[Int]]
edit boolss intss = zipWith (zipWith leaveIf) boolss intss

EDIT: You'd like to only change one, so we'll need a way of making subsequent Falses into Trues:

makeTrue :: [Bool] -> [Bool]
makeTrue xs = map (const True) xs

I've used the function const :: a -> b -> a. For example, const 5 'c' is just 5. I could shorten that definition to makeTrue = map (const True). Once you get used to thinking that way, you'll find the shorter version clearer.

oneFalse :: [[Bool]] -> [[Bool]]
oneFalse [] = []
oneFalse (xs:xss) = let (trues,falses) = break (==False) xs in
     case falses of 
       [] -> trues:oneFalse xss
       (False:others) -> (trues ++ False : makeTrue others) : map makeTrue xss

(==False) could be written more simply as not, but less clearly perhaps. so for example

> oneFalse [[True,True,True,True],[True,False,True,False],[True,False,False,True]]
[[True,True,True,True],[True,False,True,True],[True,True,True,True]]

So now we can have

editOne :: [[Bool]] -> [[Int]] -> [[Int]]
editOne boolss intss = zipWith (zipWith leaveIf) (oneFalse boolss) intss

Upvotes: 2

Lars Noschinski
Lars Noschinski

Reputation: 3667

AndrewC already gave an solution which changed all 1s corresponding to Falses. If we only want to correct the first one, we have to find a replacement for zipWith:

leaveIf ok x = if ok then x else 1 -x

-- Varianto of zipWith, which changes at most one element of the list
modFirst :: Eq b => (a -> b -> b) -> [a] -> [b] -> [b]
modFirst _ [] _ = []
modFirst _ _ [] = []
modFirst f (x:xs) (y:ys) = z : if y == z then modFirst f xs ys else ys
  where z = f x y

edit :: [[Bool]] -> [[Int]] -> [[Int]]
edit boolss intss = modFirst (modFirst leaveIf) boolss intss

correct' :: [[Int]] -> [[Int]]
correct' xss = edit (correct' xss) xss

The result is the not necessarily a list of lists where all lines/rows contain an even number of 1's:

correct' [[0,1,0],[1,1,1],[0,1,0]] = [[1,1,0],[1,1,1],[0,1,0]

You need to iterate it a few times, until all errors are fixed (i.e., compute a fixpoint).

I'd like to add that your original program can be simplified quite a bit (without changing your algorithm):

parityLine :: [[Int]] -> [Bool]
parityLine = map (even . sum)

parityColumn :: [Int] -> [Bool]
parityColumn = map even

sumPositions :: [[Int]] -> [Int]
sumPositions = foldl (zipWith (+)) (repeat 0)

bol :: [Bool] -> [Bool] -> [[Bool]]
bol xs ys = map (\x -> map (||x) ys) xs

correct :: [[Int]] -> [[Bool]]
correct xs = bol (parityLine xs) (parityColumn $ sumPositions xs)

Upvotes: 2

Related Questions