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

----------------------------------------------------------------
--                                                  ~ 2011.02.12
-- |
-- Module      :  Data.Trie.Convenience
-- Copyright   :  Copyright (c) 2008--2015 wren gayle romano
-- License     :  BSD3
-- Maintainer  :  wren@community.haskell.org
-- Stability   :  experimental
-- Portability :  portable
--
-- Additional convenience functions. In order to keep "Data.Trie"
-- concise, non-essential and uncommonly used functions have been
-- moved here. Most of these functions simplify the generic functions
-- from "Data.Trie", following after the interface for "Data.Map"
-- and "Data.IntMap".
----------------------------------------------------------------

module Data.Trie.Convenience
    (
    -- * Conversion functions ('fromList' variants)
    -- $fromList
      fromListL, fromListR, fromListS
    , fromListWith,  fromListWith'
    , fromListWithL, fromListWithL'

    -- * Query functions ('lookupBy' variants)
    , lookupWithDefault

    -- * Inserting values ('alterBy' variants)
    , insertIfAbsent
    , insertWith,    insertWith'
    , insertWithKey, insertWithKey'

    -- * Updating and adjusting values ('alterBy' and 'adjustBy' variants)
    , adjustWithKey
    , update, updateWithKey

    -- * Combining tries ('mergeBy' variants)
    , disunion
    , unionWith, unionWith'
    ) where

import Data.Trie
import Data.Trie.Internal (lookupBy_, adjustBy)
import Data.Trie.Errors   (impossible)
import Data.ByteString    (ByteString)
import Data.List          (foldl', sortBy)
import Data.Ord           (comparing)

----------------------------------------------------------------
----------------------------------------------------------------
-- $fromList
-- Just like 'fromList' all of these functions convert an association
-- list into a trie, with earlier values shadowing later ones when
-- keys conflict. Depending on the order of keys in the list, there
-- can be as much as 5x speed difference between the left and right
-- variants. Yet, performance is about the same when matching
-- best-case to best-case and worst-case to worst-case (which is
-- which is swapped when reversing the list or changing which
-- function is used).


-- | A left-fold version of 'fromList'. If you run into issues with
-- stack overflows when using 'fromList' or 'fromListR', then you
-- should use this function instead.
fromListL :: [(ByteString,a)] -> Trie a
{-# INLINE fromListL #-}
fromListL :: [(ByteString, a)] -> Trie a
fromListL = (Trie a -> (ByteString, a) -> Trie a)
-> Trie a -> [(ByteString, a)] -> Trie a
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (((ByteString, a) -> Trie a -> Trie a)
-> Trie a -> (ByteString, a) -> Trie a
forall a b c. (a -> b -> c) -> b -> a -> c
flip (((ByteString, a) -> Trie a -> Trie a)
 -> Trie a -> (ByteString, a) -> Trie a)
-> ((ByteString -> a -> Trie a -> Trie a)
    -> (ByteString, a) -> Trie a -> Trie a)
-> (ByteString -> a -> Trie a -> Trie a)
-> Trie a
-> (ByteString, a)
-> Trie a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (ByteString -> a -> Trie a -> Trie a)
-> (ByteString, a) -> Trie a -> Trie a
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry ((ByteString -> a -> Trie a -> Trie a)
 -> Trie a -> (ByteString, a) -> Trie a)
-> (ByteString -> a -> Trie a -> Trie a)
-> Trie a
-> (ByteString, a)
-> Trie a
forall a b. (a -> b) -> a -> b
$ ByteString -> a -> Trie a -> Trie a
forall a. ByteString -> a -> Trie a -> Trie a
insertIfAbsent) Trie a
forall a. Trie a
empty


-- | An explicitly right-fold variant of 'fromList'. It is a good
-- consumer for list fusion. Worst-case behavior is somewhat worse
-- than worst-case for 'fromListL'. The 'fromList' function is
-- currently just an alias for 'fromListR'.
fromListR :: [(ByteString,a)] -> Trie a
{-# INLINE fromListR #-}
fromListR :: [(ByteString, a)] -> Trie a
fromListR = [(ByteString, a)] -> Trie a
forall a. [(ByteString, a)] -> Trie a
fromList -- == foldr (uncurry insert) empty


-- TODO: compare performance against a fromListL variant, adjusting the sort appropriately
--
-- | This variant sorts the list before folding over it. This adds
-- /O(n log n)/ overhead and requires the whole list be in memory
-- at once, but it ensures that the list is in best-case order. The
-- benefits generally outweigh the costs.
fromListS :: [(ByteString,a)] -> Trie a
{-# INLINE fromListS #-}
fromListS :: [(ByteString, a)] -> Trie a
fromListS = [(ByteString, a)] -> Trie a
forall a. [(ByteString, a)] -> Trie a
fromListR ([(ByteString, a)] -> Trie a)
-> ([(ByteString, a)] -> [(ByteString, a)])
-> [(ByteString, a)]
-> Trie a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((ByteString, a) -> (ByteString, a) -> Ordering)
-> [(ByteString, a)] -> [(ByteString, a)]
forall a. (a -> a -> Ordering) -> [a] -> [a]
sortBy (((ByteString, a) -> ByteString)
-> (ByteString, a) -> (ByteString, a) -> Ordering
forall a b. Ord a => (b -> a) -> b -> b -> Ordering
comparing (ByteString, a) -> ByteString
forall a b. (a, b) -> a
fst)


-- | A variant of 'fromListR' that takes a function for combining
-- values on conflict. The first argument to the combining function
-- is the \"new\" value from the initial portion of the list; the
-- second argument is the value that has been accumulated into the
-- trie from the tail of the list (just like the first argument to
-- 'foldr'). Thus, @fromList = fromListWith const@.
fromListWith :: (a -> a -> a) -> [(ByteString,a)] -> Trie a
{-# INLINE fromListWith #-}
fromListWith :: (a -> a -> a) -> [(ByteString, a)] -> Trie a
fromListWith a -> a -> a
f = ((ByteString, a) -> Trie a -> Trie a)
-> Trie a -> [(ByteString, a)] -> Trie a
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr ((ByteString -> a -> Trie a -> Trie a)
-> (ByteString, a) -> Trie a -> Trie a
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry ((ByteString -> a -> Trie a -> Trie a)
 -> (ByteString, a) -> Trie a -> Trie a)
-> (ByteString -> a -> Trie a -> Trie a)
-> (ByteString, a)
-> Trie a
-> Trie a
forall a b. (a -> b) -> a -> b
$ (ByteString -> a -> Maybe a -> Maybe a)
-> ByteString -> a -> Trie a -> Trie a
forall a.
(ByteString -> a -> Maybe a -> Maybe a)
-> ByteString -> a -> Trie a -> Trie a
alterBy ByteString -> a -> Maybe a -> Maybe a
forall p. p -> a -> Maybe a -> Maybe a
g) Trie a
forall a. Trie a
empty
    where
    g :: p -> a -> Maybe a -> Maybe a
g p
_ a
v Maybe a
Nothing  = a -> Maybe a
forall a. a -> Maybe a
Just a
v
    g p
_ a
v (Just a
w) = a -> Maybe a
forall a. a -> Maybe a
Just (a -> a -> a
f a
v a
w)


-- | A variant of 'fromListWith' which applies the combining
-- function strictly. This function is a good consumer for list
-- fusion. If you need list fusion and are running into stack
-- overflow problems with 'fromListWith', then this function may
-- solve the problem.
fromListWith' :: (a -> a -> a) -> [(ByteString,a)] -> Trie a
{-# INLINE fromListWith' #-}
fromListWith' :: (a -> a -> a) -> [(ByteString, a)] -> Trie a
fromListWith' a -> a -> a
f = ((ByteString, a) -> Trie a -> Trie a)
-> Trie a -> [(ByteString, a)] -> Trie a
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr ((ByteString -> a -> Trie a -> Trie a)
-> (ByteString, a) -> Trie a -> Trie a
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry ((ByteString -> a -> Trie a -> Trie a)
 -> (ByteString, a) -> Trie a -> Trie a)
-> (ByteString -> a -> Trie a -> Trie a)
-> (ByteString, a)
-> Trie a
-> Trie a
forall a b. (a -> b) -> a -> b
$ (ByteString -> a -> Maybe a -> Maybe a)
-> ByteString -> a -> Trie a -> Trie a
forall a.
(ByteString -> a -> Maybe a -> Maybe a)
-> ByteString -> a -> Trie a -> Trie a
alterBy ByteString -> a -> Maybe a -> Maybe a
forall p. p -> a -> Maybe a -> Maybe a
g') Trie a
forall a. Trie a
empty
    where
    g' :: p -> a -> Maybe a -> Maybe a
g' p
_ a
v Maybe a
Nothing  = a -> Maybe a
forall a. a -> Maybe a
Just a
v
    g' p
_ a
v (Just a
w) = a -> Maybe a
forall a. a -> Maybe a
Just (a -> Maybe a) -> a -> Maybe a
forall a b. (a -> b) -> a -> b
$! a -> a -> a
f a
v a
w


-- | A left-fold variant of 'fromListWith'. Note that the arguments
-- to the combining function are swapped: the first is the value
-- in the trie which has been accumulated from the initial part of
-- the list; the second argument is the \"new\" value from the
-- remaining tail of the list (just like the first argument to
-- 'foldl'). Thus, @fromListL = fromListWithL const@.
fromListWithL :: (a -> a -> a) -> [(ByteString,a)] -> Trie a
{-# INLINE fromListWithL #-}
fromListWithL :: (a -> a -> a) -> [(ByteString, a)] -> Trie a
fromListWithL a -> a -> a
f = (Trie a -> (ByteString, a) -> Trie a)
-> Trie a -> [(ByteString, a)] -> Trie a
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (((ByteString, a) -> Trie a -> Trie a)
-> Trie a -> (ByteString, a) -> Trie a
forall a b c. (a -> b -> c) -> b -> a -> c
flip (((ByteString, a) -> Trie a -> Trie a)
 -> Trie a -> (ByteString, a) -> Trie a)
-> ((ByteString -> a -> Trie a -> Trie a)
    -> (ByteString, a) -> Trie a -> Trie a)
-> (ByteString -> a -> Trie a -> Trie a)
-> Trie a
-> (ByteString, a)
-> Trie a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (ByteString -> a -> Trie a -> Trie a)
-> (ByteString, a) -> Trie a -> Trie a
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry ((ByteString -> a -> Trie a -> Trie a)
 -> Trie a -> (ByteString, a) -> Trie a)
-> (ByteString -> a -> Trie a -> Trie a)
-> Trie a
-> (ByteString, a)
-> Trie a
forall a b. (a -> b) -> a -> b
$ (ByteString -> a -> Maybe a -> Maybe a)
-> ByteString -> a -> Trie a -> Trie a
forall a.
(ByteString -> a -> Maybe a -> Maybe a)
-> ByteString -> a -> Trie a -> Trie a
alterBy ByteString -> a -> Maybe a -> Maybe a
forall p. p -> a -> Maybe a -> Maybe a
flipG) Trie a
forall a. Trie a
empty
    where
    flipG :: p -> a -> Maybe a -> Maybe a
flipG p
_ a
v Maybe a
Nothing  = a -> Maybe a
forall a. a -> Maybe a
Just a
v
    flipG p
_ a
v (Just a
w) = a -> Maybe a
forall a. a -> Maybe a
Just (a -> a -> a
f a
w a
v)


-- | A variant of 'fromListWithL' which applies the combining
-- function strictly.
fromListWithL' :: (a -> a -> a) -> [(ByteString,a)] -> Trie a
{-# INLINE fromListWithL' #-}
fromListWithL' :: (a -> a -> a) -> [(ByteString, a)] -> Trie a
fromListWithL' a -> a -> a
f = (Trie a -> (ByteString, a) -> Trie a)
-> Trie a -> [(ByteString, a)] -> Trie a
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl' (((ByteString, a) -> Trie a -> Trie a)
-> Trie a -> (ByteString, a) -> Trie a
forall a b c. (a -> b -> c) -> b -> a -> c
flip (((ByteString, a) -> Trie a -> Trie a)
 -> Trie a -> (ByteString, a) -> Trie a)
-> ((ByteString -> a -> Trie a -> Trie a)
    -> (ByteString, a) -> Trie a -> Trie a)
-> (ByteString -> a -> Trie a -> Trie a)
-> Trie a
-> (ByteString, a)
-> Trie a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (ByteString -> a -> Trie a -> Trie a)
-> (ByteString, a) -> Trie a -> Trie a
forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry ((ByteString -> a -> Trie a -> Trie a)
 -> Trie a -> (ByteString, a) -> Trie a)
-> (ByteString -> a -> Trie a -> Trie a)
-> Trie a
-> (ByteString, a)
-> Trie a
forall a b. (a -> b) -> a -> b
$ (ByteString -> a -> Maybe a -> Maybe a)
-> ByteString -> a -> Trie a -> Trie a
forall a.
(ByteString -> a -> Maybe a -> Maybe a)
-> ByteString -> a -> Trie a -> Trie a
alterBy ByteString -> a -> Maybe a -> Maybe a
forall p. p -> a -> Maybe a -> Maybe a
flipG') Trie a
forall a. Trie a
empty
    where
    flipG' :: p -> a -> Maybe a -> Maybe a
flipG' p
_ a
v Maybe a
Nothing  = a -> Maybe a
forall a. a -> Maybe a
Just a
v
    flipG' p
_ a
v (Just a
w) = a -> Maybe a
forall a. a -> Maybe a
Just (a -> Maybe a) -> a -> Maybe a
forall a b. (a -> b) -> a -> b
$! a -> a -> a
f a
w a
v

----------------------------------------------------------------
-- | Lookup a key, returning a default value if it's not found.
lookupWithDefault :: a -> ByteString -> Trie a -> a
lookupWithDefault :: a -> ByteString -> Trie a -> a
lookupWithDefault a
def = (Maybe a -> Trie a -> a)
-> a -> (Trie a -> a) -> ByteString -> Trie a -> a
forall a b.
(Maybe a -> Trie a -> b)
-> b -> (Trie a -> b) -> ByteString -> Trie a -> b
lookupBy_ Maybe a -> Trie a -> a
forall p. Maybe a -> p -> a
f a
def (a -> Trie a -> a
forall a b. a -> b -> a
const a
def)
    where
    f :: Maybe a -> p -> a
f Maybe a
Nothing  p
_ = a
def
    f (Just a
v) p
_ = a
v

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

-- | Insert a new key, retaining old value on conflict.
insertIfAbsent :: ByteString -> a -> Trie a -> Trie a
insertIfAbsent :: ByteString -> a -> Trie a -> Trie a
insertIfAbsent =
    (ByteString -> a -> Maybe a -> Maybe a)
-> ByteString -> a -> Trie a -> Trie a
forall a.
(ByteString -> a -> Maybe a -> Maybe a)
-> ByteString -> a -> Trie a -> Trie a
alterBy ((ByteString -> a -> Maybe a -> Maybe a)
 -> ByteString -> a -> Trie a -> Trie a)
-> (ByteString -> a -> Maybe a -> Maybe a)
-> ByteString
-> a
-> Trie a
-> Trie a
forall a b. (a -> b) -> a -> b
$ \ByteString
_ a
x Maybe a
mv ->
        case Maybe a
mv of
        Maybe a
Nothing -> a -> Maybe a
forall a. a -> Maybe a
Just a
x
        Just a
_  -> Maybe a
mv

-- | Insert a new key, with a function to resolve conflicts.
insertWith :: (a -> a -> a) -> ByteString -> a -> Trie a -> Trie a
insertWith :: (a -> a -> a) -> ByteString -> a -> Trie a -> Trie a
insertWith a -> a -> a
f =
    (ByteString -> a -> Maybe a -> Maybe a)
-> ByteString -> a -> Trie a -> Trie a
forall a.
(ByteString -> a -> Maybe a -> Maybe a)
-> ByteString -> a -> Trie a -> Trie a
alterBy ((ByteString -> a -> Maybe a -> Maybe a)
 -> ByteString -> a -> Trie a -> Trie a)
-> (ByteString -> a -> Maybe a -> Maybe a)
-> ByteString
-> a
-> Trie a
-> Trie a
forall a b. (a -> b) -> a -> b
$ \ByteString
_ a
x Maybe a
mv ->
        case Maybe a
mv of
        Maybe a
Nothing -> a -> Maybe a
forall a. a -> Maybe a
Just a
x
        Just a
v  -> a -> Maybe a
forall a. a -> Maybe a
Just (a -> a -> a
f a
x a
v)

-- | A variant of 'insertWith' which applies the combining function
-- strictly.
insertWith' :: (a -> a -> a) -> ByteString -> a -> Trie a -> Trie a
insertWith' :: (a -> a -> a) -> ByteString -> a -> Trie a -> Trie a
insertWith' a -> a -> a
f =
    (ByteString -> a -> Maybe a -> Maybe a)
-> ByteString -> a -> Trie a -> Trie a
forall a.
(ByteString -> a -> Maybe a -> Maybe a)
-> ByteString -> a -> Trie a -> Trie a
alterBy ((ByteString -> a -> Maybe a -> Maybe a)
 -> ByteString -> a -> Trie a -> Trie a)
-> (ByteString -> a -> Maybe a -> Maybe a)
-> ByteString
-> a
-> Trie a
-> Trie a
forall a b. (a -> b) -> a -> b
$ \ByteString
_ a
x Maybe a
mv ->
        case Maybe a
mv of
        Maybe a
Nothing -> a -> Maybe a
forall a. a -> Maybe a
Just a
x
        Just a
v  -> a -> Maybe a
forall a. a -> Maybe a
Just (a -> Maybe a) -> a -> Maybe a
forall a b. (a -> b) -> a -> b
$! a -> a -> a
f a
x a
v

-- | A variant of 'insertWith' which also provides the key to the
-- combining function.
insertWithKey :: (ByteString -> a -> a -> a) -> ByteString -> a -> Trie a -> Trie a
insertWithKey :: (ByteString -> a -> a -> a) -> ByteString -> a -> Trie a -> Trie a
insertWithKey ByteString -> a -> a -> a
f =
    (ByteString -> a -> Maybe a -> Maybe a)
-> ByteString -> a -> Trie a -> Trie a
forall a.
(ByteString -> a -> Maybe a -> Maybe a)
-> ByteString -> a -> Trie a -> Trie a
alterBy ((ByteString -> a -> Maybe a -> Maybe a)
 -> ByteString -> a -> Trie a -> Trie a)
-> (ByteString -> a -> Maybe a -> Maybe a)
-> ByteString
-> a
-> Trie a
-> Trie a
forall a b. (a -> b) -> a -> b
$ \ByteString
k a
x Maybe a
mv ->
        case Maybe a
mv of
        Maybe a
Nothing -> a -> Maybe a
forall a. a -> Maybe a
Just a
x
        Just a
v  -> a -> Maybe a
forall a. a -> Maybe a
Just (ByteString -> a -> a -> a
f ByteString
k a
x a
v)

-- | A variant of 'insertWithKey' which applies the combining
-- function strictly.
insertWithKey' :: (ByteString -> a -> a -> a) -> ByteString -> a -> Trie a -> Trie a
insertWithKey' :: (ByteString -> a -> a -> a) -> ByteString -> a -> Trie a -> Trie a
insertWithKey' ByteString -> a -> a -> a
f =
    (ByteString -> a -> Maybe a -> Maybe a)
-> ByteString -> a -> Trie a -> Trie a
forall a.
(ByteString -> a -> Maybe a -> Maybe a)
-> ByteString -> a -> Trie a -> Trie a
alterBy ((ByteString -> a -> Maybe a -> Maybe a)
 -> ByteString -> a -> Trie a -> Trie a)
-> (ByteString -> a -> Maybe a -> Maybe a)
-> ByteString
-> a
-> Trie a
-> Trie a
forall a b. (a -> b) -> a -> b
$ \ByteString
k a
x Maybe a
mv ->
        case Maybe a
mv of
        Maybe a
Nothing -> a -> Maybe a
forall a. a -> Maybe a
Just a
x
        Just a
v  -> a -> Maybe a
forall a. a -> Maybe a
Just (a -> Maybe a) -> a -> Maybe a
forall a b. (a -> b) -> a -> b
$! ByteString -> a -> a -> a
f ByteString
k a
x a
v

{- This is a tricky one...
insertLookupWithKey :: (ByteString -> a -> a -> a) -> ByteString -> a -> Trie a -> (Maybe a, Trie a)
-}

----------------------------------------------------------------
-- | Apply a function to change the value at a key.
adjustWithKey :: (ByteString -> a -> a) -> ByteString -> Trie a -> Trie a
adjustWithKey :: (ByteString -> a -> a) -> ByteString -> Trie a -> Trie a
adjustWithKey ByteString -> a -> a
f ByteString
q =
    (ByteString -> a -> a -> a) -> ByteString -> a -> Trie a -> Trie a
forall a.
(ByteString -> a -> a -> a) -> ByteString -> a -> Trie a -> Trie a
adjustBy (\ByteString
k a
_ -> ByteString -> a -> a
f ByteString
k) ByteString
q (String -> a
forall a. String -> a
impossible String
"Convenience.adjustWithKey")
-- TODO: benchmark vs the definition with alterBy/liftM

-- | Apply a function to the value at a key, possibly removing it.
update :: (a -> Maybe a) -> ByteString -> Trie a -> Trie a
update :: (a -> Maybe a) -> ByteString -> Trie a -> Trie a
update a -> Maybe a
f ByteString
q =
    (ByteString -> a -> Maybe a -> Maybe a)
-> ByteString -> a -> Trie a -> Trie a
forall a.
(ByteString -> a -> Maybe a -> Maybe a)
-> ByteString -> a -> Trie a -> Trie a
alterBy (\ByteString
_ a
_ Maybe a
mx -> Maybe a
mx Maybe a -> (a -> Maybe a) -> Maybe a
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= a -> Maybe a
f) ByteString
q (String -> a
forall a. String -> a
impossible String
"Convenience.update")

-- | A variant of 'update' which also provides the key to the function.
updateWithKey :: (ByteString -> a -> Maybe a) -> ByteString -> Trie a -> Trie a
updateWithKey :: (ByteString -> a -> Maybe a) -> ByteString -> Trie a -> Trie a
updateWithKey ByteString -> a -> Maybe a
f ByteString
q =
    (ByteString -> a -> Maybe a -> Maybe a)
-> ByteString -> a -> Trie a -> Trie a
forall a.
(ByteString -> a -> Maybe a -> Maybe a)
-> ByteString -> a -> Trie a -> Trie a
alterBy (\ByteString
k a
_ Maybe a
mx -> Maybe a
mx Maybe a -> (a -> Maybe a) -> Maybe a
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= ByteString -> a -> Maybe a
f ByteString
k) ByteString
q (String -> a
forall a. String -> a
impossible String
"Convenience.updateWithKey")

{-
updateLookupWithKey :: (ByteString -> a -> Maybe a) -> ByteString -> Trie a -> (Maybe a, Trie a)
-- Also tricky
-}

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

-- | Combine two tries, a la symmetric difference. If they define
-- the same key, it is removed; otherwise it is retained with the
-- value it has in whichever trie.
disunion :: Trie a -> Trie a -> Trie a
disunion :: Trie a -> Trie a -> Trie a
disunion = (a -> a -> Maybe a) -> Trie a -> Trie a -> Trie a
forall a. (a -> a -> Maybe a) -> Trie a -> Trie a -> Trie a
mergeBy (\a
_ a
_ -> Maybe a
forall a. Maybe a
Nothing)

-- | Combine two tries, using a function to resolve conflicts.
unionWith :: (a -> a -> a) -> Trie a -> Trie a -> Trie a
unionWith :: (a -> a -> a) -> Trie a -> Trie a -> Trie a
unionWith a -> a -> a
f = (a -> a -> Maybe a) -> Trie a -> Trie a -> Trie a
forall a. (a -> a -> Maybe a) -> Trie a -> Trie a -> Trie a
mergeBy (\a
x a
y -> a -> Maybe a
forall a. a -> Maybe a
Just (a -> a -> a
f a
x a
y))

-- | A variant of 'unionWith' which applies the combining function
-- strictly.
unionWith' :: (a -> a -> a) -> Trie a -> Trie a -> Trie a
unionWith' :: (a -> a -> a) -> Trie a -> Trie a -> Trie a
unionWith' a -> a -> a
f = (a -> a -> Maybe a) -> Trie a -> Trie a -> Trie a
forall a. (a -> a -> Maybe a) -> Trie a -> Trie a -> Trie a
mergeBy (\a
x a
y -> a -> Maybe a
forall a. a -> Maybe a
Just (a -> Maybe a) -> a -> Maybe a
forall a b. (a -> b) -> a -> b
$! a -> a -> a
f a
x a
y)

{- TODO: (efficiently)
difference, intersection
-}

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