Stable marriage in Haskell
import Safe (findJust)
import Data.Foldable (null, all)

personalRating = sortBy . comparing . defaultRateFunction

proposal m f = all (on (&gt;) (defaultRateFunction f) m) $ partner f

remarry p x = (x {partner = p} :) . delete x

marrige :: [Person] -&gt; [Person] -&gt; [Person]
marrige ms fs = case find (null . partner) ms of
  Nothing -&gt; fs
  Just m -&gt; marrige
    (remarry (Just f} m $ maybe id (remarry Nothing) (partner f) ms)
    (remarry (Just m) f fs)
    where f = findJust (proposal m) $ personalRating m fs


You never actually use ms that have a partner. Why keep track of them? I'll assume that all start out without partners, otherwise filter once at the start. In particular, I'll assume the invariant that partnership is symmetric.

marrige :: [Person] -&gt; [Person] -&gt; [Person]
marrige [] fs = fs
marriage (m:ms) fs = marrige 
  (maybe id (\ex -&gt; (ex {partner = Nothing} :)) (partner f) ms)
  (f {partner = Just m} : delete f fs)
    where f = findJust (proposal m) $ personalRating m fs


For performance, you could use Data.Map instead of []'s delete.

Edit: Here's one where the explicit recursion is less global. Unsetting ex's partner may be superfluous.

import Control.Monad.State

marrige = execState . traverse_ go where go m = do
  f &lt;- gets $ findJust (proposal m) . personalRating m
  modify $ (f {partner = Just m} :) . delete f
  for_ (partner f) $ \ex -&gt; go $ ex {partner = Nothing}