Handling multiple dimensions of arrays with speed

Question

I'm looking to learn how to write efficient Haskell code. This snippet works, but the run time is slow. How can I write faster Haskell code?

Input: maxPrice = 7

Input: vendorsDelivery = [5, 4, 2, 3]

Input: vendorsProducts = [[1, 1, 1],[3, -1, 3],[-1, 2, 2],[5, -1, -1]]

Output: [1,2] (fastest delivery time for a given order)

import Data.List
import Data.List.Split
import Control.Monad

data Vendor a = Vendor { vendorNbr :: Int
                       , deliveryTime :: Int
                       , itemPrice :: Int
                       } deriving (Show)

populate d v = map (filter (\x -> itemPrice x /= (-1))) $ transpose $ map (\(x,y,z) -> map (\xs -> Vendor x y xs) z) $ zip3 [0..] d v 

minimalBasketPrice mP vD vP = nub . get1 $ foldr (\x xs -> if get2 x < (get2 xs) then x else xs) (possible !! 0) possible
    where combos = sequence (populate vD vP) 
          possible = filter (\(_,_,x) -> x <= mP) [((accu vendorNbr y), (total deliveryTime y), (total itemPrice y)) | y <- combos]

-- | Helper Functions 

get1 (x,_,_) = x
get2 (_,x,_) = x

total f = foldr (\x y -> (f x) + y) 0
accu f = foldr (\x y -> (f x) : y) []

Answer 1

Have some rewrite rules applied, combinators used and helpers inlined while I think about your algorithmic question. And make Vendor a newtype.

minimalBasketPrice mP vD
  = nub
  . map vendorNbr
  . minimumOn (sum . map deliveryTime)
  . filter ((<= mP) . sum . map itemPrice)
  . sequence
  . (map . filter) ((/= -1) . itemPrice)
  . transpose
  . zipWith3 (\x y -> map (Vendor x y)) [0..] vD

This is the backpack problem and NP-hard. We won't be scaling well in the worst-case whatever we do, but we can do a little better by, for example, only keeping track of suffixes of vendor selections that can't be undercut in time and price at the same time:

newtype Candidate a = Candidate
  { vendors :: [Int]
  , time :: Int
  , price :: Int 
  }

minimalBasketPrice mP vD
  = nub . vendors . head
  . foldr (foo mP) [Candidate [] 0 0]
  . map (filter ((/= -1) . itemPrice))
  . transpose
  . zipWith3 (\x y -> map (Vendor x y)) [0..] vD

foo :: Int -> [Vendor] -> [Candidate] -> [Candidate]
foo mP choices
  = catMaybes . snd
  . mapAccumL bar (mP+1)
  . sortOn time
  . liftA2 addVendor choices

bar :: Int -> Candidate -> (Int, Maybe Candidate)
bar bestprice candidate = if price candidate < bestprice
  then (price candidate, Just candidate)
  else (bestprice, Nothing)

addVendor (Vendor v t p) (Candidate vs ts ps) = Candidate (v:vs) (t+ts) (p+ps)