{-# OPTIONS_GHC -Wall -fwarn-tabs #-}
{-# LANGUAGE CPP #-}
#if __GLASGOW_HASKELL__ >= 701
{-# LANGUAGE Safe #-}
#endif
----------------------------------------------------------------
--                                                  ~ 2021.12.14
-- |
-- Module      :  Data.Trie.Convenience
-- Copyright   :  2008--2021 wren romano
-- License     :  BSD-3-Clause
-- Maintainer  :  wren@cpan.org
-- Stability   :  provisional
-- 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' and 'intersectBy' variants)
    , disunion
    , unionWith, unionWith'
    , intersectWith, intersectWith'
    ) where

import Data.Trie
import Data.Trie.Internal (lookupBy_, alterBy_)
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
-- \(\mathcal{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.
--
-- @since 0.2.3
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@.
--
-- @since 0.2.3
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.
--
-- @since 0.2.3
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 = (a -> Trie a -> a)
-> (Trie a -> a) -> a -> ByteString -> Trie a -> a
forall a b.
(a -> Trie a -> b)
-> (Trie a -> b) -> b -> ByteString -> Trie a -> b
lookupBy_ a -> Trie a -> a
forall a b. a -> b -> a
const (a -> Trie a -> a
forall a b. a -> b -> a
const a
def) a
def

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

-- | 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.
--
-- @since 0.2.3
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.
--
-- @since 0.2.3
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 = (a -> a) -> ByteString -> Trie a -> Trie a
forall a. (a -> a) -> ByteString -> Trie a -> Trie a
adjust (ByteString -> a -> a
f ByteString
q) ByteString
q

-- | 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 = (Maybe a -> Trie a -> (Maybe a, Trie a))
-> ByteString -> Trie a -> Trie a
forall a.
(Maybe a -> Trie a -> (Maybe a, Trie a))
-> ByteString -> Trie a -> Trie a
alterBy_ (\Maybe a
mx Trie a
t -> (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, Trie a
t)) ByteString
q

-- | 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 = (Maybe a -> Trie a -> (Maybe a, Trie a))
-> ByteString -> Trie a -> Trie a
forall a.
(Maybe a -> Trie a -> (Maybe a, Trie a))
-> ByteString -> Trie a -> Trie a
alterBy_ (\Maybe a
mx Trie a
t -> (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
q, Trie a
t)) ByteString
q

{-
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)

-- | Take the union of two tries, using a function to resolve
-- conflicts.  The resulting trie is constructed strictly, but the
-- results of the combining function are evaluated lazily.
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 evaluates the combining function
-- strictly.
--
-- @since 0.2.3
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)

-- | Take the intersection of two tries, with a function to resolve
-- the values.  The resulting trie is constructed strictly, bit the
-- results of the combining function are evaluated lazily.
--
-- @since 0.2.6
intersectWith :: (a -> b -> c) -> Trie a -> Trie b -> Trie c
intersectWith :: (a -> b -> c) -> Trie a -> Trie b -> Trie c
intersectWith a -> b -> c
f = (a -> b -> Maybe c) -> Trie a -> Trie b -> Trie c
forall a b c. (a -> b -> Maybe c) -> Trie a -> Trie b -> Trie c
intersectBy (\a
x b
y -> c -> Maybe c
forall a. a -> Maybe a
Just (a -> b -> c
f a
x b
y))

-- | A variant of 'intersectWith' which evaluates the combining
-- function strictly.
--
-- @since 0.2.6
intersectWith' :: (a -> b -> c) -> Trie a -> Trie b -> Trie c
intersectWith' :: (a -> b -> c) -> Trie a -> Trie b -> Trie c
intersectWith' a -> b -> c
f = (a -> b -> Maybe c) -> Trie a -> Trie b -> Trie c
forall a b c. (a -> b -> Maybe c) -> Trie a -> Trie b -> Trie c
intersectBy (\a
x b
y -> c -> Maybe c
forall a. a -> Maybe a
Just (c -> Maybe c) -> c -> Maybe c
forall a b. (a -> b) -> a -> b
$! a -> b -> c
f a
x b
y)

-- TODO(github#23): add 'difference' (efficiently!)

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