1
\$\begingroup\$

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) []
\$\endgroup\$
  • \$\begingroup\$ 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?) \$\endgroup\$ – Gurkenglas Dec 31 '16 at 6:07
  • \$\begingroup\$ 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] \$\endgroup\$ – Jonathan Portorreal Dec 31 '16 at 7:09
  • 1
    \$\begingroup\$ 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.) \$\endgroup\$ – Gurkenglas Dec 31 '16 at 7:24
  • \$\begingroup\$ 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. \$\endgroup\$ – Jonathan Portorreal Dec 31 '16 at 7:50
  • \$\begingroup\$ 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. \$\endgroup\$ – Jonathan Portorreal Dec 31 '16 at 7:56
4
\$\begingroup\$

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)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.