CODEWITHSUNDEEP
haskellfunctional-programming
lachrimae
lachrimae

Reputation: 79

Is there a way to rewrite this function to be total?

I have a function, shown below, which someone on Code Review suggested I rewrite to be total. They suggested that the calls to getRow and (!) could be replaced with calls to zip or fold.

I've thought about this and I can't really see how to rewrite it that way, nor do I have a good sense of how I would teach myself how to rewrite it. 

import Data.Matrix (Matrix, getRow, ncols)
import Data.Vector ((!))

type AdjacencyMatrix = Matrix Bool

-- Input: the graph's adjacency matrix and a vertex. 
-- Output: the list of neighbours of that vertex.
neighbours :: AdjacencyMatrix -> Int -> [Int]
neighbours mat n = filter (\m -> row ! m) [0..(ncols mat)-1]
        where row = getRow n mat

This code snippet works within the context of my program, but if n is larger than (ncols mat) - 1 then some of the row ! m calls will fail.

Upvotes: 3

Views: 119

Answers (1)

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476614

You can make use of safeGetRow :: Matrix a -> Maybe (Vector a) that will return a Nothing in case the index is out of range.

The question is of course what we do in case the index is out of range. Two reasonable options are:

  1. use Maybe [Int] instead of [Int] as return type and return a Nothing; or
  2. return an empty list, since if the node is not in the adjacency matrix, it has no neignbors.

We can for example implement this as:

import Data.Matrix(Matrix, safeGetRow)
import Data.Vector(toList)

neighbours :: AdjacencyMatrix -> Int -> Maybe [Int]
neighbours mat n = map fst . filter snd . zip [0..] . toList <$> safeGetRow n mat

We here make use of toList :: Vector a -> [a] to prevent using (!) :: Vector a -> Int -> a which looks unsafe: you used correc indices, but this requires some reasoning, whereas toList is a total function, and thus clearly will always produce a result.

We can make this more compact by using findIndices :: (a -> Bool) -> Vector a -> Vector Int:

import Data.Matrix(Matrix, safeGetRow)
import Data.Vector(findIndices, toList)

neighbours :: AdjacencyMatrix -> Int -> Maybe [Int]
neighbours mat n = toList . findIndices id <$> safeGetRow n mat

Or we can use maybe :: b -> (a -> b) -> Maybe a -> b to use an empty list instead:

import Data.Matrix(Matrix, safeGetRow)
import Data.Maybe(maybe)
import Data.Vector(findIndices, toList)

neighbours :: AdjacencyMatrix -> Int -> [Int]
neighbours mat n = maybe [] (toList . findIndices id) (safeGetRow n mat)

Upvotes: 5

Related Questions