{-# LANGUAGE FunctionalDependencies, Safe #-}

{-|
Module      : Dep.Class.NonDeterministicWalkable
Description : A module that exposes a type class that allows /non-deterministic/ "walking" through a data structure.
Maintainer  : hapytexeu+gh@gmail.com
Stability   : experimental
Portability : POSIX

This module defines a typeclass 'NonDeterministicWalkable' that specifies that one can walk through a non-deterministic
data structure where a certain step can result in zero, one, or more new states.
-}

module Dep.Class.NonDeterministicWalkable (
    -- * Non determinstic steps and walks
    NonDeterministicWalkable(nstep', nstep, nstepValues, nstepValues', nwalk, nwalkValues, allNstep, allNstep', allNwalk, allNstepValues, allNwalkValues)
  ) where

import Dep.Utils(toList')

import Control.Monad(foldM)

-- | A typeclass that specifies that we can walk through the given datastructure
-- where steps can be non-deterministic and thus result in /multiple/ possible states.
class NonDeterministicWalkable f step | f -> step where
  -- | Take a non-deterministic step that can result in multiple outcomes.
  -- One can specify a tail to make concatenating of lists more efficient.
  nstep'
    :: f a  -- ^ The given initial state where we make a non-determinstic step.
    -> step  -- ^ The step that we make, such step can result in zero, one or more new states.
    -> [f a]  -- ^ The list of tail elements added to the result.
    -> [f a]  -- ^ The list of the possible states with the new step.
  nstep' f a
x step
dx = (f a -> step -> [f a]
forall (f :: * -> *) step a.
NonDeterministicWalkable f step =>
f a -> step -> [f a]
nstep f a
x step
dx [f a] -> [f a] -> [f a]
forall a. [a] -> [a] -> [a]
++)

  -- | Take a non-deterministic step that can result in multiple outcomes.
  nstep
    :: f a  -- ^ The given initial state where we make a non-determinstic step.
    -> step  -- ^ The step that we make, such step can result in zero, one or more new states.
    -> [f a]  -- ^ The list of the possible states with the new step.
  nstep f a
x step
dx = f a -> step -> [f a] -> [f a]
forall (f :: * -> *) step a.
NonDeterministicWalkable f step =>
f a -> step -> [f a] -> [f a]
nstep' f a
x step
dx []

  -- | Obtain the values stored in the 'Foldable' after making a non-deterministic
  -- step (which can result in zero, one or more new states).
  nstepValues' :: Foldable f
    => f a  -- ^ The initial state.
    -> step  -- ^ The non-deterministic step we take.
    -> [a]  -- ^ The list of tail elements that will be added to the list.
    -> [a]  -- ^ A list of values wrapped in the 'Foldable's after making a non-deterministic step.
  nstepValues' f a
st step
stp = ([a] -> [f a] -> [a]) -> [f a] -> [a] -> [a]
forall a b c. (a -> b -> c) -> b -> a -> c
flip ((f a -> [a] -> [a]) -> [a] -> [f a] -> [a]
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr f a -> [a] -> [a]
forall (f :: * -> *) a. Foldable f => f a -> [a] -> [a]
toList') (f a -> step -> [f a]
forall (f :: * -> *) step a.
NonDeterministicWalkable f step =>
f a -> step -> [f a]
nstep f a
st step
stp)

  -- | Obtain the values stored in the 'Foldable' after making a non-deterministic
  -- step (which can result in zero, one or more new states).
  nstepValues :: Foldable f
    => f a  -- ^ The initial state.
    -> step  -- ^ The non-deterministic step we take.
    -> [a]  -- ^ A list of values wrapped in the 'Foldable's after making a non-deterministic step.
  nstepValues f a
st step
stp = f a -> step -> [a] -> [a]
forall (f :: * -> *) step a.
(NonDeterministicWalkable f step, Foldable f) =>
f a -> step -> [a] -> [a]
nstepValues' f a
st step
stp []


  -- | Take the same non-deterministic step for all initial states.
  -- This can result in multiple outcomes. One can specify a tail to
  -- make concatenating of lists more efficient.
  allNstep' :: Foldable g
    => g (f a)  -- ^ The given initial state where we make a non-determinstic step.
    -> step  -- ^ The step that we make, such step can result in zero, one or more new states.
    -> [f a]  -- ^ The list of tail elements added to the result.
    -> [f a]  -- ^ The list of the possible states with the new step.
  allNstep' g (f a)
xs step
dx [f a]
tl = (f a -> [f a] -> [f a]) -> [f a] -> g (f a) -> [f a]
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (f a -> step -> [f a] -> [f a]
forall (f :: * -> *) step a.
NonDeterministicWalkable f step =>
f a -> step -> [f a] -> [f a]
`nstep'` step
dx) [f a]
tl g (f a)
xs

  -- | Take the same non-deterministic step for all initial states.
  -- This can result in multiple outcomes.
  allNstep :: Foldable g
    => g (f a)  -- ^ The given initial state where we make a non-determinstic step.
    -> step  -- ^ The step that we make, such step can result in zero, one or more new states.
    -> [f a]  -- ^ The list of the possible states with the new step.
  allNstep g (f a)
xs step
dx = g (f a) -> step -> [f a] -> [f a]
forall (f :: * -> *) step (g :: * -> *) a.
(NonDeterministicWalkable f step, Foldable g) =>
g (f a) -> step -> [f a] -> [f a]
allNstep' g (f a)
xs step
dx []

  -- | Make a non-deterministic step for each state in the collection,
  -- and collect the data of the 'Foldable's after making.
  allNstepValues :: Foldable f
    => [f a] -- ^ The initial states for te walk.
    -> step -- ^ The non-deterministic step we make.
    -> [a] -- ^ The resulting (possible) values that are stored in the final foldables.
  allNstepValues [f a]
inis step
stps = [f a]
inis [f a] -> (f a -> [a]) -> [a]
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= (f a -> step -> [a]
forall (f :: * -> *) step a.
(NonDeterministicWalkable f step, Foldable f) =>
f a -> step -> [a]
`nstepValues` step
stps)

  -- Make a walk with non-deterministic steps that can result in multiple paths.
  nwalk :: Foldable g
    => f a -- ^ The initial state of the walk.
    -> g step -- ^ A 'Foldable' of steps that we take.
    -> [f a] -- ^ The resulting (possible) states after taking the walk.
  nwalk = (f a -> step -> [f a]) -> f a -> g step -> [f a]
forall (t :: * -> *) (m :: * -> *) b a.
(Foldable t, Monad m) =>
(b -> a -> m b) -> b -> t a -> m b
foldM f a -> step -> [f a]
forall (f :: * -> *) step a.
NonDeterministicWalkable f step =>
f a -> step -> [f a]
nstep

  -- Make a walk with non-deterministic steps that can result in multiple paths.
  -- After the walk all the states will report the values wrapped in the 'Foldable'.
  nwalkValues :: (Foldable f, Foldable g)
    => f a -- ^ The initial state of the walk.
    -> g step -- ^ A 'Foldable' of steps that we take.
    -> [a] -- ^ The resulting (possible) values that are stored in the final foldables.
  nwalkValues f a
ini g step
stps = (f a -> [a] -> [a]) -> [a] -> [f a] -> [a]
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr f a -> [a] -> [a]
forall (f :: * -> *) a. Foldable f => f a -> [a] -> [a]
toList' [] ((f a -> step -> [f a]) -> f a -> g step -> [f a]
forall (t :: * -> *) (m :: * -> *) b a.
(Foldable t, Monad m) =>
(b -> a -> m b) -> b -> t a -> m b
foldM f a -> step -> [f a]
forall (f :: * -> *) step a.
NonDeterministicWalkable f step =>
f a -> step -> [f a]
nstep f a
ini g step
stps)


  -- | Make a non-deterministic walk with a collection of states that can result in multiple paths.
  allNwalk :: Foldable g
    => [f a] -- ^ The initial states for te walk.
    -> g step -- ^ A 'Foldable' of steps that we will take.
    -> [f a] -- The resulting list of possible states.
  allNwalk = (((f a -> [f a]) -> [f a])
-> (g step -> f a -> [f a]) -> g step -> [f a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (f a -> g step -> [f a]) -> g step -> f a -> [f a]
forall a b c. (a -> b -> c) -> b -> a -> c
flip f a -> g step -> [f a]
forall (f :: * -> *) step (g :: * -> *) a.
(NonDeterministicWalkable f step, Foldable g) =>
f a -> g step -> [f a]
nwalk) (((f a -> [f a]) -> [f a]) -> g step -> [f a])
-> ([f a] -> (f a -> [f a]) -> [f a]) -> [f a] -> g step -> [f a]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [f a] -> (f a -> [f a]) -> [f a]
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
(>>=)

  -- | Make a non-deterministic walk with a collection of states that can result in multiple paths.
  allNwalkValues :: (Foldable f, Foldable g)
    => [f a] -- ^ The initial states for te walk.
    -> g step -- ^ A 'Foldable' of steps that we will take.
    -> [a] -- ^ The resulting (possible) values that are stored in the final foldables.
  allNwalkValues [f a]
inis g step
stps = [f a]
inis [f a] -> (f a -> [a]) -> [a]
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= (f a -> g step -> [a]
forall (f :: * -> *) step (g :: * -> *) a.
(NonDeterministicWalkable f step, Foldable f, Foldable g) =>
f a -> g step -> [a]
`nwalkValues` g step
stps)
  {-# MINIMAL nstep' | nstep #-}