# 3-function program computing connected components of a point cloud given a distance matrix

I wrote this code in Haskell (instead of Python) for the educational benefit. Can anyone suggest ways to improve this code?

I'm guessing that I'm using fromIntegral inefficiently.

It takes two commandline arguments. The first is a path to a symmetric distance matrix. The second is a threshold. The program interprets vertices to be adjacent if their distance is less than the threshold. Then the program counts the number of connected components and the number of vertices in each connected component and prints this information.

import System.Environment
import Data.Matrix hiding (flatten)
import qualified Data.Vector as V
import Data.Graph
import Data.Tree

-- Turns a distance matrix to an adjacency matrix using a threshold, then prints the number
-- and size of the connected components.
-- Usage: run stack run location_of_distance_matrix threshold
-- Output is in the form (number of bins, [number of vertices in each bin]).
main :: IO ()
main = do
args <- getArgs
contents <- readFile $args !! 0 let dmat = fromLists$ (map ((map (read :: String -> Float)) . words) (lines contents))
amat    = amatFromDmat dmat $read (args !! 1) (g,_,_) = graphFromEdges (map (\n -> (n, n, neighbours n amat)) [(1 :: Integer)..(fromIntegral$ ncols amat)])
comp    = components g
putStrLn $show$ (length comp, map (length . flatten) comp)

-- Transforms a distance matrix into an adjacency matrix using a threshold.
amatFromDmat :: Matrix Float -> Float -> Matrix Bool
amatFromDmat m e = matrix (nrows m) (ncols m) threshold
where threshold (i,j)
| i == j         = False
| m ! (i,j) < e  = True
| otherwise      = False

-- Outputs the list of neighbours of a vertex in a graph, taking an adjacency
-- matrix.
-- The addition and subtraction of 1 are here because vectors are 0-indexed but
-- I made my graph vertices 1-indexed.
neighbours :: Integer -> Matrix Bool -> [Integer]
neighbours n mat = map (fromIntegral . (1+)) \$ filter (\m -> row V.! m) [0..(ncols mat)-1]
where row = getRow (fromIntegral n) mat


Edit: I found a bug and improved the code a little bit.

1. "Functional core, imperative shell": Move more code out of main (and out of IO) into separate (pure) functions. The type signatures on the extracted functions will help with readability.
2. Use types to model your domain. Haskell makes it easy to define expressive types, you should make use of that feature! :) For example, you could define type AdjacencyMatrix = Matrix Float.
3. The Int <-> Integer conversions look unnecessary to me. Just stick to Int since the Data.Matrix API forces you to use it anyway.
4. In general, it's a good idea to use as few partial functions as possible. (I see (!!), (Data.Vector.!), read, getRow and fromInteger) Since this is a script, using read for parsing is acceptable. Instead of indexing with (Data.Vector.!) and getRow, I'd try to map, fold or zip instead, which usually are total operations. Instead of extracting the command line arguments with (!!), you could write [filename, threshold] <- getArgs.
5. amatFromDmat smells functorial to me, mostly because the input and output matrices have the same dimensions. Maybe try to implement it in terms of fmap. (Hint: If the input is a true distance matrix, the elements on the diagonal are the only ones that are 0.)
7. Tree has a Foldable instance and length is a method of Foldable. That means you can simply use length to get the size of the connected components. You don't need flatten.
• What is it about the [filename, threshold] <- getArgs option that avoids a total operation? And I'm very excited by your functoriality suggestion--I'm studying category theory on the math side and I want to see how to bring it to bear on my programming! – Curran McConnell May 21 '19 at 22:25
• Yeah, that's not a great example. You could argue that replacing (!) with a partial pattern in IO (which would trigger fail) you move the partiality out of pure code, and into a MonadFail where failures happen anyway. In these circumstances it doesn't really matter. – sjakobi May 21 '19 at 22:52
• Just implemented amatFromDmat using fmap. My mind is like: media.giphy.com/media/THFoDqDi4M92w/giphy.gif – Curran McConnell May 22 '19 at 1:08