{-# LANGUAGE CPP #-}
{-# LANGUAGE GADTs #-}
{-# LANGUAGE Rank2Types #-}
{-# LANGUAGE FlexibleContexts #-}

#ifdef TRUSTWORTHY
{-# LANGUAGE Trustworthy #-} -- vector, hashable
#endif

#include "lens-common.h"

-------------------------------------------------------------------------------
-- |
-- Module      :  Control.Lens.Indexed
-- Copyright   :  (C) 2012-16 Edward Kmett
-- License     :  BSD-style (see the file LICENSE)
-- Maintainer  :  Edward Kmett <ekmett@gmail.com>
-- Stability   :  provisional
-- Portability :  Rank2Types
--
-- (The classes in here need to be defined together for @DefaultSignatures@ to work.)
-------------------------------------------------------------------------------
module Control.Lens.Indexed
  (
  -- * Indexing
    Indexable(..)
  , Conjoined(..)
  , Indexed(..)
  , (<.), (<.>), (.>)
  , selfIndex
  , reindexed
  , icompose
  , indexing
  , indexing64
  -- * Indexed Functors
  , FunctorWithIndex(..)
  -- ** Indexed Functor Combinators
  , imapped
  -- * Indexed Foldables
  , FoldableWithIndex(..)
  -- ** Indexed Foldable Combinators
  , ifolded
  , iany
  , iall
  , inone, none
  , itraverse_
  , ifor_
  , imapM_
  , iforM_
  , iconcatMap
  , ifind
  , ifoldrM
  , ifoldlM
  , itoList
  -- * Converting to Folds
  , withIndex
  , asIndex
  -- * Restricting by Index
  , indices
  , index
  -- * Indexed Traversables
  , TraversableWithIndex(..)
  -- * Indexed Traversable Combinators
  , itraversed
  , ifor
  , imapM
  , iforM
  , imapAccumR
  , imapAccumL
  -- * Indexed Folds with Reified Monoid
  , ifoldMapBy
  , ifoldMapByOf
  -- * Indexed Traversals with Reified Applicative
  , itraverseBy
  , itraverseByOf
  ) where

import Prelude ()

import Data.Functor.WithIndex
import Data.Foldable.WithIndex
import Data.Traversable.WithIndex

import Control.Lens.Fold
import Control.Lens.Getter
import Control.Lens.Internal.Fold
import Control.Lens.Internal.Indexed
import Control.Lens.Internal.Prelude
import Control.Lens.Setter
import Control.Lens.Traversal
import Control.Lens.Type
import Data.Reflection

import Data.HashMap.Lazy (HashMap)
import Data.IntMap (IntMap)
import Data.Map (Map)
import Data.Sequence (Seq)
import Data.Vector (Vector)

import qualified Data.HashMap.Lazy as HashMap
import qualified Data.IntMap as IntMap
import qualified Data.Map as Map
import qualified Data.Sequence as Seq
import qualified Data.Vector as Vector

infixr 9 <.>, <., .>

-- $setup
-- >>> :set -XNoOverloadedStrings
-- >>> import Control.Lens
-- >>> import qualified Data.Map as Map

-- | Compose an 'Indexed' function with a non-indexed function.
--
-- Mnemonically, the @<@ points to the indexing we want to preserve.
--
-- >>> let nestedMap = (fmap Map.fromList . Map.fromList) [(1, [(10, "one,ten"), (20, "one,twenty")]), (2, [(30, "two,thirty"), (40,"two,forty")])]
-- >>> nestedMap^..(itraversed<.itraversed).withIndex
-- [(1,"one,ten"),(1,"one,twenty"),(2,"two,thirty"),(2,"two,forty")]
(<.) :: Indexable i p => (Indexed i s t -> r) -> ((a -> b) -> s -> t) -> p a b -> r
<. :: forall i (p :: * -> * -> *) s t r a b.
Indexable i p =>
(Indexed i s t -> r) -> ((a -> b) -> s -> t) -> p a b -> r
(<.) Indexed i s t -> r
f (a -> b) -> s -> t
g p a b
h = Indexed i s t -> r
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall i a b. (i -> a -> b) -> Indexed i a b
Indexed forall a b. (a -> b) -> a -> b
$ (a -> b) -> s -> t
g forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall i (p :: * -> * -> *) a b.
Indexable i p =>
p a b -> i -> a -> b
indexed p a b
h
{-# INLINE (<.) #-}

-- | Compose a non-indexed function with an 'Indexed' function.
--
-- Mnemonically, the @>@ points to the indexing we want to preserve.
--
-- This is the same as @('.')@.
--
-- @f '.' g@ (and @f '.>' g@) gives you the index of @g@ unless @g@ is index-preserving, like a
-- 'Prism', 'Iso' or 'Equality', in which case it'll pass through the index of @f@.
--
-- >>> let nestedMap = (fmap Map.fromList . Map.fromList) [(1, [(10, "one,ten"), (20, "one,twenty")]), (2, [(30, "two,thirty"), (40,"two,forty")])]
-- >>> nestedMap^..(itraversed.>itraversed).withIndex
-- [(10,"one,ten"),(20,"one,twenty"),(30,"two,thirty"),(40,"two,forty")]
(.>) :: (st -> r) -> (kab -> st) -> kab -> r
.> :: forall b c a. (b -> c) -> (a -> b) -> a -> c
(.>) = forall b c a. (b -> c) -> (a -> b) -> a -> c
(.)
{-# INLINE (.>) #-}

-- | Use a value itself as its own index. This is essentially an indexed version of 'id'.
--
-- Note: When used to modify the value, this can break the index requirements assumed by 'indices' and similar,
-- so this is only properly an 'IndexedGetter', but it can be used as more.
--
-- @
-- 'selfIndex' :: 'IndexedGetter' a a b
-- @
selfIndex :: Indexable a p => p a fb -> a -> fb
selfIndex :: forall a (p :: * -> * -> *) fb. Indexable a p => p a fb -> a -> fb
selfIndex p a fb
f a
a = forall i (p :: * -> * -> *) a b.
Indexable i p =>
p a b -> i -> a -> b
indexed p a fb
f a
a a
a
{-# INLINE selfIndex #-}

-- | Remap the index.
reindexed :: Indexable j p => (i -> j) -> (Indexed i a b -> r) -> p a b -> r
reindexed :: forall j (p :: * -> * -> *) i a b r.
Indexable j p =>
(i -> j) -> (Indexed i a b -> r) -> p a b -> r
reindexed i -> j
ij Indexed i a b -> r
f p a b
g = Indexed i a b -> r
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall i a b. (i -> a -> b) -> Indexed i a b
Indexed forall a b. (a -> b) -> a -> b
$ forall i (p :: * -> * -> *) a b.
Indexable i p =>
p a b -> i -> a -> b
indexed p a b
g forall b c a. (b -> c) -> (a -> b) -> a -> c
. i -> j
ij
{-# INLINE reindexed #-}

-- | Composition of 'Indexed' functions.
--
-- Mnemonically, the @\<@ and @\>@ points to the fact that we want to preserve the indices.
--
-- >>> let nestedMap = (fmap Map.fromList . Map.fromList) [(1, [(10, "one,ten"), (20, "one,twenty")]), (2, [(30, "two,thirty"), (40,"two,forty")])]
-- >>> nestedMap^..(itraversed<.>itraversed).withIndex
-- [((1,10),"one,ten"),((1,20),"one,twenty"),((2,30),"two,thirty"),((2,40),"two,forty")]
(<.>) :: Indexable (i, j) p => (Indexed i s t -> r) -> (Indexed j a b -> s -> t) -> p a b -> r
Indexed i s t -> r
f <.> :: forall i j (p :: * -> * -> *) s t r a b.
Indexable (i, j) p =>
(Indexed i s t -> r) -> (Indexed j a b -> s -> t) -> p a b -> r
<.> Indexed j a b -> s -> t
g = forall p (c :: * -> * -> *) i j s t r a b.
Indexable p c =>
(i -> j -> p)
-> (Indexed i s t -> r) -> (Indexed j a b -> s -> t) -> c a b -> r
icompose (,) Indexed i s t -> r
f Indexed j a b -> s -> t
g
{-# INLINE (<.>) #-}

-- | Composition of 'Indexed' functions with a user supplied function for combining indices.
icompose :: Indexable p c => (i -> j -> p) -> (Indexed i s t -> r) -> (Indexed j a b -> s -> t) -> c a b -> r
icompose :: forall p (c :: * -> * -> *) i j s t r a b.
Indexable p c =>
(i -> j -> p)
-> (Indexed i s t -> r) -> (Indexed j a b -> s -> t) -> c a b -> r
icompose i -> j -> p
ijk Indexed i s t -> r
istr Indexed j a b -> s -> t
jabst c a b
cab = Indexed i s t -> r
istr forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall i a b. (i -> a -> b) -> Indexed i a b
Indexed forall a b. (a -> b) -> a -> b
$ \i
i -> Indexed j a b -> s -> t
jabst forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall i a b. (i -> a -> b) -> Indexed i a b
Indexed forall a b. (a -> b) -> a -> b
$ \j
j -> forall i (p :: * -> * -> *) a b.
Indexable i p =>
p a b -> i -> a -> b
indexed c a b
cab forall a b. (a -> b) -> a -> b
$ i -> j -> p
ijk i
i j
j
{-# INLINE icompose #-}

-------------------------------------------------------------------------------
-- Restricting by index
-------------------------------------------------------------------------------

-- | This allows you to filter an 'IndexedFold', 'IndexedGetter', 'IndexedTraversal' or 'IndexedLens' based on a predicate
-- on the indices.
--
-- >>> ["hello","the","world","!!!"]^..traversed.indices even
-- ["hello","world"]
--
-- >>> over (traversed.indices (>0)) Prelude.reverse $ ["He","was","stressed","o_O"]
-- ["He","saw","desserts","O_o"]
indices :: (Indexable i p, Applicative f) => (i -> Bool) -> Optical' p (Indexed i) f a a
indices :: forall i (p :: * -> * -> *) (f :: * -> *) a.
(Indexable i p, Applicative f) =>
(i -> Bool) -> Optical' p (Indexed i) f a a
indices i -> Bool
p p a (f a)
f = forall i a b. (i -> a -> b) -> Indexed i a b
Indexed forall a b. (a -> b) -> a -> b
$ \i
i a
a -> if i -> Bool
p i
i then forall i (p :: * -> * -> *) a b.
Indexable i p =>
p a b -> i -> a -> b
indexed p a (f a)
f i
i a
a else forall (f :: * -> *) a. Applicative f => a -> f a
pure a
a
{-# INLINE indices #-}

-- | This allows you to filter an 'IndexedFold', 'IndexedGetter', 'IndexedTraversal' or 'IndexedLens' based on an index.
--
-- >>> ["hello","the","world","!!!"]^?traversed.index 2
-- Just "world"
index :: (Indexable i p, Eq i, Applicative f) => i -> Optical' p (Indexed i) f a a
index :: forall i (p :: * -> * -> *) (f :: * -> *) a.
(Indexable i p, Eq i, Applicative f) =>
i -> Optical' p (Indexed i) f a a
index i
j p a (f a)
f = forall i a b. (i -> a -> b) -> Indexed i a b
Indexed forall a b. (a -> b) -> a -> b
$ \i
i a
a -> if i
j forall a. Eq a => a -> a -> Bool
== i
i then forall i (p :: * -> * -> *) a b.
Indexable i p =>
p a b -> i -> a -> b
indexed p a (f a)
f i
i a
a else forall (f :: * -> *) a. Applicative f => a -> f a
pure a
a
{-# INLINE index #-}


-------------------------------------------------------------------------------
-- FunctorWithIndex
-------------------------------------------------------------------------------

-- | The 'IndexedSetter' for a 'FunctorWithIndex'.
--
-- If you don't need access to the index, then 'mapped' is more flexible in what it accepts.
imapped :: FunctorWithIndex i f => IndexedSetter i (f a) (f b) a b
imapped :: forall i (f :: * -> *) a b.
FunctorWithIndex i f =>
IndexedSetter i (f a) (f b) a b
imapped = forall (p :: * -> * -> *) (q :: * -> * -> *) a b r.
Conjoined p =>
((p ~ (->)) => q (a -> b) r) -> q (p a b) r -> q (p a b) r
conjoined forall (f :: * -> *) a b. Functor f => Setter (f a) (f b) a b
mapped (forall i a b s t.
((i -> a -> b) -> s -> t) -> IndexedSetter i s t a b
isets forall i (f :: * -> *) a b.
FunctorWithIndex i f =>
(i -> a -> b) -> f a -> f b
imap)
{-# INLINE imapped #-}

-------------------------------------------------------------------------------
-- FoldableWithIndex
-------------------------------------------------------------------------------

-- | The 'IndexedFold' of a 'FoldableWithIndex' container.
--
-- @'ifolded' '.' 'asIndex'@ is a fold over the keys of a 'FoldableWithIndex'.
--
-- >>> Data.Map.fromList [(2, "hello"), (1, "world")]^..ifolded.asIndex
-- [1,2]
ifolded :: FoldableWithIndex i f => IndexedFold i (f a) a
ifolded :: forall i (f :: * -> *) a.
FoldableWithIndex i f =>
IndexedFold i (f a) a
ifolded = forall (p :: * -> * -> *) (q :: * -> * -> *) a b r.
Conjoined p =>
((p ~ (->)) => q (a -> b) r) -> q (p a b) r -> q (p a b) r
conjoined forall (f :: * -> *) a. Foldable f => IndexedFold Int (f a) a
folded forall a b. (a -> b) -> a -> b
$ \p a (f a)
f -> forall (f :: * -> *) a b.
(Functor f, Contravariant f) =>
f a -> f b
phantom forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (f :: * -> *) a. Folding f a -> f a
getFolding forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall i (f :: * -> *) m a.
(FoldableWithIndex i f, Monoid m) =>
(i -> a -> m) -> f a -> m
ifoldMap (\i
i -> forall (f :: * -> *) a. f a -> Folding f a
Folding forall (p :: * -> * -> *) a b c (q :: * -> * -> *).
(Profunctor p, Coercible c b) =>
q b c -> p a b -> p a c
#. forall i (p :: * -> * -> *) a b.
Indexable i p =>
p a b -> i -> a -> b
indexed p a (f a)
f i
i)
{-# INLINE ifolded #-}

-------------------------------------------------------------------------------
-- TraversableWithIndex
-------------------------------------------------------------------------------

-- | The 'IndexedTraversal' of a 'TraversableWithIndex' container.
itraversed :: TraversableWithIndex i t => IndexedTraversal i (t a) (t b) a b
itraversed :: forall i (t :: * -> *) a b.
TraversableWithIndex i t =>
IndexedTraversal i (t a) (t b) a b
itraversed = forall (p :: * -> * -> *) (q :: * -> * -> *) a b r.
Conjoined p =>
((p ~ (->)) => q (a -> b) r) -> q (p a b) r -> q (p a b) r
conjoined forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse (forall i (t :: * -> *) (f :: * -> *) a b.
(TraversableWithIndex i t, Applicative f) =>
(i -> a -> f b) -> t a -> f (t b)
itraverse forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall i (p :: * -> * -> *) a b.
Indexable i p =>
p a b -> i -> a -> b
indexed)
{-# INLINE [0] itraversed #-}

-------------------------------------------------------------------------------
-- Instances
-------------------------------------------------------------------------------

{-# RULES
"itraversed -> mapList"    itraversed = sets fmap        :: ASetter [a] [b] a b;
"itraversed -> imapList"   itraversed = isets imap       :: AnIndexedSetter Int [a] [b] a b;
"itraversed -> foldrList"  itraversed = foldring foldr   :: Getting (Endo r) [a] a;
"itraversed -> ifoldrList" itraversed = ifoldring ifoldr :: IndexedGetting Int (Endo r) [a] a;
 #-}

{-# RULES
"itraversed -> mapIntMap"    itraversed = sets IntMap.map               :: ASetter (IntMap a) (IntMap b) a b;
"itraversed -> imapIntMap"   itraversed = isets IntMap.mapWithKey       :: AnIndexedSetter Int (IntMap a) (IntMap b) a b;
"itraversed -> foldrIntMap"  itraversed = foldring IntMap.foldr         :: Getting (Endo r) (IntMap a) a;
"itraversed -> ifoldrIntMap" itraversed = ifoldring IntMap.foldrWithKey :: IndexedGetting Int (Endo r) (IntMap a) a;
 #-}

{-# RULES
"itraversed -> mapMap"    itraversed = sets Map.map               :: ASetter (Map k a) (Map k b) a b;
"itraversed -> imapMap"   itraversed = isets Map.mapWithKey       :: AnIndexedSetter k (Map k a) (Map k b) a b;
"itraversed -> foldrMap"  itraversed = foldring Map.foldr         :: Getting (Endo r) (Map k a) a;
"itraversed -> ifoldrMap" itraversed = ifoldring Map.foldrWithKey :: IndexedGetting k (Endo r) (Map k a) a;
 #-}

{-# RULES
"itraversed -> mapHashMap"    itraversed = sets HashMap.map               :: ASetter (HashMap k a) (HashMap k b) a b;
"itraversed -> imapHashMap"   itraversed = isets HashMap.mapWithKey       :: AnIndexedSetter k (HashMap k a) (HashMap k b) a b;
"itraversed -> foldrHashMap"  itraversed = foldring HashMap.foldr         :: Getting (Endo r) (HashMap k a) a;
"itraversed -> ifoldrHashMap" itraversed = ifoldring HashMap.foldrWithKey :: IndexedGetting k (Endo r) (HashMap k a) a;
 #-}

{-# RULES
"itraversed -> mapSeq"    itraversed = sets fmap                    :: ASetter (Seq a) (Seq b) a b;
"itraversed -> imapSeq"   itraversed = isets Seq.mapWithIndex       :: AnIndexedSetter Int (Seq a) (Seq b) a b;
"itraversed -> foldrSeq"  itraversed = foldring foldr               :: Getting (Endo r) (Seq a) a;
"itraversed -> ifoldrSeq" itraversed = ifoldring Seq.foldrWithIndex :: IndexedGetting Int (Endo r) (Seq a) a;
 #-}

{-# RULES
"itraversed -> mapVector"    itraversed = sets Vector.map         :: ASetter (Vector a) (Vector b) a b;
"itraversed -> imapVector"   itraversed = isets Vector.imap       :: AnIndexedSetter Int (Vector a) (Vector b) a b;
"itraversed -> foldrVector"  itraversed = foldring Vector.foldr   :: Getting (Endo r) (Vector a) a;
"itraversed -> ifoldrVector" itraversed = ifoldring Vector.ifoldr :: IndexedGetting Int (Endo r) (Vector a) a;
 #-}

-------------------------------------------------------------------------------
-- Indexed Folds with Reified Monoid
-------------------------------------------------------------------------------

ifoldMapBy :: FoldableWithIndex i t => (r -> r -> r) -> r -> (i -> a -> r) -> t a -> r
ifoldMapBy :: forall i (t :: * -> *) r a.
FoldableWithIndex i t =>
(r -> r -> r) -> r -> (i -> a -> r) -> t a -> r
ifoldMapBy r -> r -> r
f r
z i -> a -> r
g = forall a t.
(a -> a -> a)
-> a
-> (forall s.
    Reifies s (ReifiedMonoid a) =>
    t -> ReflectedMonoid a s)
-> t
-> a
reifyMonoid r -> r -> r
f r
z (forall i (f :: * -> *) m a.
(FoldableWithIndex i f, Monoid m) =>
(i -> a -> m) -> f a -> m
ifoldMap (\i
i a
a -> forall {k} a (s :: k). a -> ReflectedMonoid a s
ReflectedMonoid (i -> a -> r
g i
i a
a)))

ifoldMapByOf :: IndexedFold i t a -> (r -> r -> r) -> r -> (i -> a -> r) -> t -> r
ifoldMapByOf :: forall i t a r.
IndexedFold i t a -> (r -> r -> r) -> r -> (i -> a -> r) -> t -> r
ifoldMapByOf IndexedFold i t a
l r -> r -> r
f r
z i -> a -> r
g = forall a t.
(a -> a -> a)
-> a
-> (forall s.
    Reifies s (ReifiedMonoid a) =>
    t -> ReflectedMonoid a s)
-> t
-> a
reifyMonoid r -> r -> r
f r
z (forall i m s a. IndexedGetting i m s a -> (i -> a -> m) -> s -> m
ifoldMapOf IndexedFold i t a
l (\i
i a
a -> forall {k} a (s :: k). a -> ReflectedMonoid a s
ReflectedMonoid (i -> a -> r
g i
i a
a)))

itraverseBy :: TraversableWithIndex i t => (forall x. x -> f x) -> (forall x y. f (x -> y) -> f x -> f y) -> (i -> a -> f b) -> t a -> f (t b)
itraverseBy :: forall i (t :: * -> *) (f :: * -> *) a b.
TraversableWithIndex i t =>
(forall x. x -> f x)
-> (forall x y. f (x -> y) -> f x -> f y)
-> (i -> a -> f b)
-> t a
-> f (t b)
itraverseBy forall x. x -> f x
pur forall x y. f (x -> y) -> f x -> f y
app i -> a -> f b
f = forall (f :: * -> *) t a.
(forall x. x -> f x)
-> (forall x y. f (x -> y) -> f x -> f y)
-> (forall s.
    Reifies s (ReifiedApplicative f) =>
    t -> ReflectedApplicative f s a)
-> t
-> f a
reifyApplicative forall x. x -> f x
pur forall x y. f (x -> y) -> f x -> f y
app (forall i (t :: * -> *) (f :: * -> *) a b.
(TraversableWithIndex i t, Applicative f) =>
(i -> a -> f b) -> t a -> f (t b)
itraverse (\i
i a
a -> forall {k} {k1} (f :: k -> *) (s :: k1) (a :: k).
f a -> ReflectedApplicative f s a
ReflectedApplicative (i -> a -> f b
f i
i a
a)))

itraverseByOf :: IndexedTraversal i s t a b -> (forall x. x -> f x) -> (forall x y. f (x -> y) -> f x -> f y) -> (i -> a -> f b) -> s -> f t
itraverseByOf :: forall i s t a b (f :: * -> *).
IndexedTraversal i s t a b
-> (forall x. x -> f x)
-> (forall x y. f (x -> y) -> f x -> f y)
-> (i -> a -> f b)
-> s
-> f t
itraverseByOf IndexedTraversal i s t a b
l forall x. x -> f x
pur forall x y. f (x -> y) -> f x -> f y
app i -> a -> f b
f = forall (f :: * -> *) t a.
(forall x. x -> f x)
-> (forall x y. f (x -> y) -> f x -> f y)
-> (forall s.
    Reifies s (ReifiedApplicative f) =>
    t -> ReflectedApplicative f s a)
-> t
-> f a
reifyApplicative forall x. x -> f x
pur forall x y. f (x -> y) -> f x -> f y
app (forall i a (f :: * -> *) b s t.
(Indexed i a (f b) -> s -> f t) -> (i -> a -> f b) -> s -> f t
itraverseOf IndexedTraversal i s t a b
l (\i
i a
a -> forall {k} {k1} (f :: k -> *) (s :: k1) (a :: k).
f a -> ReflectedApplicative f s a
ReflectedApplicative (i -> a -> f b
f i
i a
a)))