Haskell iterate through each 2x2 grid over a list of list and apply function

user_15515713 0
Viewed 252

suppose I have a list of list xs. Each element in xs has the same length (e.g. xs is not like [[1,2],[1],[1,2,3]]). And I have a function f, which return a Bool. I want to apply f to each of the 2x2 grid in xs and get the AND result of the applications.

For example,

xs = [[1,2,3],[4,5,6],[7,8,9]]

f :: [[Int]] -> Bool
f [[1,_][_,_]] = False
f _ = True ​

In this case, I want to

  • apply f to [[1,2],[4,5]] and return False
  • apply f to [[2,3],[5,6]] and return True
  • apply f to [[4,5],[7,8]] and return True
  • apply f to [[5,6],[8,9]] and return True

Then the final result should be False as 3 Trues and 1 False result in False.

Currently I write a function that help me to extract a 2x2 grid from the list

get_grid :: [[Int]] -> [[Int]]
get_grid xs = map (take 2) (take 2 xs)

Is there any way to iterate over xs by get_grid and apply f in each iteration and AND the result?

Thanks for any help.

list haskell
1 Answers

If you write a function to get all adjacent pairs from a list:

pairs :: [a] -> [[a]]
pairs (x:y:rest) = [x,y] : pairs (y:rest)
pairs _ = []

you can apply it to your matrix to get the submatrices consistent of adjacent pairs of rows:

> pairs xs
[[[1,2,3],[4,5,6]],[[4,5,6],[7,8,9]]]

Transpose each of these submatrices:

> map transpose . pairs $ xs
[[[1,4],[2,5],[3,6]],[[4,7],[5,8],[6,9]]]

and then split them into submatrices of pairs of rows, as before:

> concatMap pairs . map transpose . pairs $ xs
[[[1,4],[2,5]],[[2,5],[3,6]],[[4,7],[5,8]],[[5,8],[6,9]]]

and transpose them back:

> map transpose . concatMap pairs . map transpose . pairs $ xs
[[[1,2],[4,5]],[[2,3],[5,6]],[[4,5],[7,8]],[[5,6],[8,9]]]

Those are the matrices you wanted, and you can check that f is true for all of them with:

> all f . map transpose . concatMap pairs . map transpose . pairs $ xs
False

A full example:

import Data.List

pairs :: [a] -> [[a]]
pairs (x:y:rest) = [x,y] : pairs (y:rest)
pairs _ = []

f :: [[Integer]] -> Bool
f [[1,_],[_,_]] = False
f _ = True

xs :: [[Integer]]
xs = [[1,2,3],[4,5,6],[7,8,9]]

ys :: [[Integer]]
ys = [[0,2,3],[4,5,6],[7,8,9]]

check_grid :: ([[a]] -> Bool) -> [[a]] -> Bool
check_grid f = all f . map transpose . concatMap pairs . map transpose . pairs

main = do
  print $ check_grid f xs
  print $ check_grid f ys
user_72030160
Related