# Space and time complexity of operation on lists

I'm new to programming and even more new to Haskell. Below is a little tid-bit I wrote that operates on a bunch of lists. I am wondering if someone would be kind enough to walk through the function margProbs line-by-line, and enumerate their respective space/time complexities and/or just possibly suggest improvements.

import qualified Control.Monad as Mo
import qualified Data.Map as M
import qualified Data.List as L
import Data.Maybe

type PaIdx = Int

margProbs :: [[Bool]] -> PaIdx ->  [Double] -> [[Double]] -> Maybe [[Double]]
margProbs bs idx vpa vs = Mo.sequence $fmap (\( _, ms ) -> collapseWith addV ms ) grouped where (p, q) = ( vpa !! 0, vpa !! 1 ) grouped = reverse . sortAndGroup$ zip ( snd probBool ) scaled
scaled   = zipWith (\p v -> scaleV (*) p v ) ( fst probBool ) vs
probBool = foldr   (\b (probs, bools) -> let (prob,bool) = reducePa b in (prob:probs, bool:bools) ) ([],[]) bs
reducePa bs = let split = fromJust $pluckL idx bs in ( if fst split == True then p else q, snd split ) ------------ -- Utils -- ------------ addV :: ( Num a ) => [a] -> [a] -> Maybe [a] addV v1 v2 = if length v1 == length v2 then Just$ zipWith (+) v1 v2 else Nothing

scaleV :: (  Num a ) => ( a -> a -> a ) -> a -> [a] -> [a]
scaleV g num v = fmap (\e -> g num e ) v

collapseWith :: ( Num a ) => ( [a] -> [a] -> Maybe [a] ) -> [[a]] -> Maybe [a]
collapseWith g vs = foldr (\v1 v2 -> v2 >>= \w -> g v1 w ) ( return $head vs ) ( tail vs ) sortAndGroup :: Ord k => [ (k, a) ] -> [ (k, [a]) ] sortAndGroup ts = M.toList$ M.fromListWith (++) [(k, [v]) | (k, v) <- ts]

pluckL :: Int -> [a] -> Maybe ( a, [a] )
pluckL idx xs = case splitAt idx xs of
( _, [] )      -> Nothing
( hs, (t:ts) ) -> Just ( t, hs ++ ts )


Here are the params I used to test this snippet:

ret = margProbs bs 0 v m
bs = [[True,True],[True,False],[False,True],[False,False]]
v = [0.4,0.6]
m = [[0.95,0.05], [0.94,0.06], [0.29,0.71], [0.1, 0.9]]


ret should have value: Just [[0.554,0.446],[0.436,0.564]]

Update

I got rid of all dependencies to the hmatrix library.

• What do you expect as an answer: suggestions to improve performance or just analysis of space&time complexity? – max taldykin Mar 19 '13 at 14:45
• Analysis of space/time complexity would be great but if simple suggestions would take less of your time, that'd be great too – chibro2 Mar 19 '13 at 15:16

scaleV

scaleV is very similar to fmap, it just has different precedence in its arguments, the following definition is simpler and highlights this similarity:

scaleV = (fmap .)


Guards

While they have the same effect of conditionals, they are preferred because they are extensible and nicer to read:

addV v1 v2 = if length v1 == length v2 then Just $zipWith (+) v1 v2 else Nothing  Becomes: addV v1 v2 | length v1 == length v2 = Just$ zipWith (+) v1 v2
| otherwise = Nothing