Distribute work evenly among participants

Work.purs

module Main where

import Prelude

import Data.List (List(..), (:), fromFoldable, sortBy, reverse)

data Task = Task String Int

sortTasksByWeightDesc :: List Task -> List Task
sortTasksByWeightDesc = sortBy compareEffort >>> reverse where
  compareEffort (Task _ a) (Task _ b) = compare a b

tasks :: List Task
tasks = fromFoldable
  [ Task "Dishes to the kitchen" 2
  , Task "Start a load of laundry" 3
  , Task "Take out recycling" 4
  , Task "Vacuum living room" 4
  , Task "Take out compost" 5
  , Task "Change laundry" 5
  , Task "Fold laundry" 6
  , Task "Load the dishwasher" 7
  ]

-- a naive function to distribute work among 3 participants...
-- step through each task (from biggest to smallest), assigning
-- it to the participant who currently has the lightest load
-- however! this simple algorithm yields 11 | 13 | 12, but
-- an optimal possible solution is 12 | 12 | 12
distributeTasks = sortTasksByWeightDesc >>> go init where
  init =
    { a: { tasks: Nil, sum: 0}
    , b: { tasks: Nil, sum: 0}
    , c: { tasks: Nil, sum: 0}
    }
    
  -- assign a task to a participant
  addTask {tasks, sum} task@(Task title weight) =
    { tasks: (task:tasks),  sum: sum + weight}
    
  -- find the participant with the lightest load and update their list
  giveToLightest members@{a, b, c} task
    | (a.sum <= b.sum && a.sum <= c.sum) = members {a = (addTask a task)}
    | (b.sum <= c.sum) = members {b = (addTask b task)}
    | otherwise = members {c = (addTask c task)}
  
  go acc Nil = acc
  go acc (x : xs) =
    go (giveToLightest acc x) xs

distributed = distributeTasks $ sortTasksByWeightDesc tasks