Pair.hs

{-# OPTIONS_GHC -Wall -fwarn-tabs #-}

----------------------------------------------------------------
--                                                  ~ 2010.05.31
-- |
-- Module      :  Data.List.Extras.Pair
-- Copyright   :  Copyright (c) 2007--2009 wren ng thornton
-- License     :  BSD3
-- Maintainer  :  wren@community.haskell.org
-- Stability   :  stable
-- Portability :  portable
--
-- This module provides safe zipping functions which will fail
-- (return 'Nothing') on uneven length lists.
----------------------------------------------------------------

module Data.List.Extras.Pair
    (
    -- * Safe functions for zipping lists
      pairWithBy, pairWith, pairBy, pair
    
    -- * Special safe zipping functions
    , biject, biject'
    
    -- * New (unsafe) zipping functions
    , zipWithBy, zipBy
    ) where


----------------------------------------------------------------
----------------------------------------------------------------
-- TODO: benchmark fusion performance of:
--
--     foldr cons nil ... zipWith (,)
--     zipWithBy (,) cons nil
--
-- ...That is, the latter is a manual fusion of the former, but
-- does zip/zipWith have a special ability to fuse with the incoming
-- lists? Or can foldr fuse with consumers in ways zipWithBy can't?

-- | An unsafe variant of 'pairWithBy' to fill out the interface.
zipWithBy :: (a -> b -> c)       -- tuple homomorphism
          -> (c -> d -> d) -> d  -- list  homomorphism
          -> [a] -> [b] -> d     -- a @zip@ function

zipWithBy k f z xs' ys' = zipWB xs' ys' id
    where
    zipWB (x:xs) (y:ys) cc = zipWB xs ys (cc . f (k x y))
    zipWB _      _      cc = cc z


-- | A version of 'zip' that uses a user-defined list homomorphism.
zipBy :: ((a,b) -> d -> d) -> d -> [a] -> [b] -> d
zipBy  = zipWithBy (,)


----------------------------------------------------------------
----------------------------------------------------------------
-- | A generic version of 'pair'. The first argument is a tuple
-- homomorphism (i.e. a function for how to combine values from the
-- two lists), the second two arguments form a list homomorphism
-- (i.e. so you can 'foldr' the @[c]@ list directly without actually
-- constructing it).
--
-- In order to evaluate to WHNF 'pairWithBy' is strict in both list
-- arguments, as it must be, to determine that the lists are of the
-- same length. This means it can survive one infinite list (yielding
-- 'Nothing') but that it can't survive two. The implementation is
-- very efficient and uses a tight tail-recursive loop, however
-- with extremely long lists it will be churning through heap and
-- that tightness can make it hard to interrupt (lists of 1 million
-- elements return in 1~2 seconds, but lists of 10 million can lock
-- your system up).

pairWithBy :: (a -> b -> c)          -- @(,)@ tuple homomorphism
           -> (c -> d -> d)          -- @(:)@ list  homomorphism, pt. 1
           -> d                      -- @[]@  list  homomorphism, pt. 2
           -> [a] -> [b] -> Maybe d  -- a safer @zip@ function

pairWithBy k f z xs' ys' = pairWB xs' ys' id
    where
    -- N.B. Strict accumulators are usually awesome, but don't
    -- even consider it when doing CPS! Making @cc@ strict degrades
    -- performance significantly; it takes twice as long and twice
    -- as much heap just to get to WHNF. After evaluating the spine
    -- of the resulting list from 'pair' that drops to +10% time
    -- and +25% heap, which is still much worse.
    
    pairWB (x:xs) (y:ys) cc = pairWB xs ys (cc . f (k x y))
    pairWB []     []     cc = Just (cc z)
    pairWB _      _      _  = Nothing

-- TODO: we could make this more general still by fusing @f@ and @k@, which we'd often want to do anyways if we're using this full form.

----------------------------------------------------------------

-- | A safe version of 'zipWith'.
pairWith  :: (a -> b -> c)
          -> [a] -> [b] -> Maybe [c]
pairWith f = pairWithBy f (:) []


-- | A safe version of 'zip' that uses a user-defined list homomorphism.
pairBy :: ((a,b) -> d -> d) -> d
       -> [a] -> [b] -> Maybe d
pairBy  = pairWithBy (,)


-- | A safe version of 'zip'.
pair :: [a] -> [b] -> Maybe [(a,b)]
pair  = pairBy (:) []


----------------------------------------------------------------
-- These two are just here because they're often requested, and
-- besides they're kinda cute.

-- | A bijection from a list of functions and a list of arguments
-- to a list of results of applying the functions bijectively.
biject :: [a -> b] -> [a] -> Maybe [b]
biject  = pairWith ($) -- 'id' also works


-- | A version of 'biject' that applies functions strictly. N.B.
-- the list is still lazily evaluated, this just makes the functions
-- strict in their argument.
biject' :: [a -> b] -> [a] -> Maybe [b]
biject'  = pairWith ($!)

----------------------------------------------------------------
----------------------------------------------------------- fin.