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) []

• Gurkenglas: Why do you nub vendor numbers, but count their delivery times from the same vendor multiple times? (Shouldn't that be the maximum of delivery times anyway, not the sum?)
• Jonathan Portorreal: Each vendor has different items, but each vendor sells the same amount of items with varying prices and I need to make sure I buy each one with the smallest delivery time. So I find the sum of all possible items and the sum of each items delivery time for each vendor. I choose the vendor combination with the smallest sum of delivery times under the max price. This would yield the array [1,2,2] and I use nub to remove the repetition of vendor 2. -> [1,2]
• Gurkenglas: The "same amount" of items? I'm asking why you count each vendor only one time for the list that you output at the end, but multiple times when you add up the delivery times. (And I also remarked that when you get multiple items delivered, you have all items after the maximum of delivery times has passed, not their sum.)
• Jonathan Portorreal: I count each vendor once as my output because the output should only show which vendors you will be shopping from if the list is [1,2,2] then you are only shopping from 1 and 2. The counting when I add up the delivery times is a consequence of how I solved the problem.
• Jonathan Portorreal: Given this line here filter (\(_,_,x) -> x <= mP) [((accu vendorNbr y), (total deliveryTime y), (total itemPrice y)) | y <- combos] I want to filter the smallest total deliveryTime of a set of items but I'm not sure how to do that without possibly removing the only possible solution from the set. I mean there could be a possible case where the only set of items you can purchase is not the smallest deliveryTime but the most expensive and in that case you'd want to return that deliveryTime.

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)