{-# 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.