Haskell - Find first 0 in a 2 dimensional array-CodePudding

Imagine you have a 2 dimensional array like this: [[1, 3, 2, 4, 5, 6, 9, 3], [3, 2, 4, 1, 6, 8, 7, 0, 9], ....] I want to get the coordinate of the first 0 value of the array -> (1, 7).

I have tried using map and elemIndex, but I'm quite new to Haskell so couldn't figure it out. A solution or some guidance would be greatly appreciated. ty :)

CodePudding user response：

When you're trying to do something to a number of items, the place to start is to work out how to do that something to just one item. Then map your function across all of the items.

Let's pick this list: [3, 2, 4, 1, 6, 8, 7, 0, 9]

The type of elemIndex can be seen in GHCi by using :t.

 :m Data.List      -- load module
 :t elemIndex      -- show type

This returns elemIndex :: Eq a => a -> [a] -> Maybe Int

So, we give it a value and a list and it returns the index as a Maybe.

 elemIndex 0 [3, 2, 4, 1, 6, 8, 7, 0, 9] -- returns Just 7

Perhaps we call this function f

 f = elemIndex 0

Then we map this function across the list of lists.

 result = map f lst

The biggest question is what you mean by the first value. If you have a list like [[1,2,3,0],[0,1,2,3]], which is the first value? That will inform how you process the results of the map.

The way that you handle a Maybe Int, is at the simplest level to match against the two value Just x and Nothing.

f :: Maybe Int -> String
f (Just x) = show x
f Nothing = "Nothing"

main = do
  putStrLn $ f (Just 3)
  putStrLn $ f (Nothing)

Using these ideas I wrote this code, which appears to do what is required. Having mapped elemIndex over the lists, I find the first matching list using findIndex. The function findIndex takes a predicate for Just x, returning True if so, and False for Nothing. Then it's just a case of matching with Just and Nothing to extract the result.

import Data.List

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

f = elemIndex 0

pJust :: Maybe a  -> Bool
pJust (Just x)  = True
pJust Nothing = False

main = do

  let results = map f lst
  let location = findIndex pJust results

  case location of
    Just index -> do
       let location2 = results !! index
       case location2 of
           Just index2 -> putStrLn $ "("    
              show index    ","   
              show index2    ")"
           Nothing -> putStrLn "Search failed"
    Nothing -> putStrLn "Search failed"

CodePudding user response：

Both elemIndex and map are quite unnecessary to solve this problem. You simply need to keep track of a set of beginning coordinates and modify it as you recursively transverse the list of lists.

Clearly, the value we're looking for can never be in an empty list, so that case will return Nothing.

If the first list in the list is empty, it also can't be there, so we go to the next list, incrementing the first coordinate and resetting the second to 0.

If that first list is not empty, we check to see if its first element is the one we're looking for. If it is, we can return the coordinates wrapped up with Just, and the recursion ends.

Otherwise, continue by incrementing the second coordinate and considering the remainder of the list of lists.

findCoords :: Eq a => (Int, Int) -> a -> [[a]] -> Maybe (Int, Int)
findCoords _ _ [] = Nothing
findCoords (i, _) v ([]:xs) = findCoords (i 1, 0) v xs
findCoords (i, j) v ((x:y):xs) 
  | v == x = Just (i, j)
  | otherwise = findCoords (i, j 1) v (y:xs)

This requires manually passing (0, 0) when called. This can be cleaned up by using a local aux function.

findCoords :: Eq a => a -> [[a]] -> Maybe (Int, Int)
findCoords = aux (0, 0)
  where
    aux _ _ [] = Nothing
    aux (i, _) v ([]:xs) = aux (i 1, 0) v xs
    aux (i, j) v ((x:y):xs) 
      | v == x = Just (i, j)
      | otherwise = aux (i, j 1) v (y:xs)