{-|

Module      : RepMax
Description : Repeat maximum element for entire list
Copyright   : © Frank Jung, 2020
License     : GPL-3

From
<https://danilafe.com/blog/haskell_lazy_evaluation/ Time Traveling In Haskell: How It Works And How To Use It> by Daniel Lafe.

Code for what Csongor calls the repMax problem:

> Imagine you had a list, and you wanted to replace all the elements of
> the list with the largest element, by only passing the list once.

How can we possibly do this in one pass? First, we need to find the maximum
element, and only then can we have something to replace the other numbers
with! It turns out, though, that we can just expect to have the future
value, and all will be well.

In the function 'repMax' takes the list of integers, each of which it must
replace with their maximum element. It also takes as an argument the
maximum element, as if it had already been computed. It does, however,
still compute the intermediate maximum element, in the form of @m'@.
Otherwise, where would the future value even come from?

Thus far, nothing too magical has happened. It’s a little strange to expect
the result of the computation to be given to us; it just looks like wishful
thinking. The real magic happens in Csongor’s 'doRepMax' function.

Look, in particular, on the line with the @where@ clause. We see that
'repMax' returns the maximum element of the list, largest, and the
resulting list @xs'@ consisting only of /largest/ repeated as many times as
@xs@ had elements. But what’s curious is the call to 'repMax' itself. It
takes as input @xs@, the list we’re supposed to process and largest, the
value that /it itself returns/.

See also <https://kcsongor.github.io/time-travel-in-haskell-for-dummies/ Time travel in Haskell for dummies>
by Csongor Kiss.

See
<https://stackoverflow.com/questions/44558242/picture-how-mapaccumr-works this>
for an explanation on how 'mapAccumR' works.

== Example

Run 'doRepMax' or 'foldMax' over some lists:

>>> doRepMax [2,3,1,4,5]
[5,5,5,5,5]

>>> doRepMax [-2,-3,-1,-4,-5]
[-1,-1,-1,-1,-1]

-}

module RepMax (doRepMax, foldMax, repMax, traverseMax, traverseMax')  where

import           Data.Foldable    (toList)
import           Data.Maybe       (fromJust)
import           Data.Monoid      (First (..), getFirst)
import           Data.Traversable (mapAccumR)

-- | Replace list with maximum value in the list.
doRepMax :: (Integral a)
              => [a]      -- ^ input list
              -> [a]      -- ^ list with elements replaced with maximum value
doRepMax :: forall a. Integral a => [a] -> [a]
doRepMax [a]
xs = [a]
xs'
  where
    (a
largest, [a]
xs') = [a] -> a -> (a, [a])
forall a. Integral a => [a] -> a -> (a, [a])
repMax [a]
xs a
largest

-- | Repeat given maximum for entire list.
repMax :: (Integral a)
            => [a]        -- ^ list to replace
            -> a          -- ^ maximum value used in replacement
            -> (a, [a])   -- ^ maximum and modified list maximum element
repMax :: forall a. Integral a => [a] -> a -> (a, [a])
repMax [] a
rep = (a
rep, [])
repMax [a
x] a
rep = (a
x, [a
rep])
repMax (a
x:[a]
xs) a
rep = (a
m', a
repa -> [a] -> [a]
forall a. a -> [a] -> [a]
:[a]
xs')
  where
    (a
m, [a]
xs') = [a] -> a -> (a, [a])
forall a. Integral a => [a] -> a -> (a, [a])
repMax [a]
xs a
rep
    m' :: a
m' = a -> a -> a
forall a. Ord a => a -> a -> a
max a
m a
x

-- | Fold version of 'repMax'.
--
-- Modified to also work with negative values.
-- /"Everything's a fold"./
foldMax :: (Integral a)
            => [a]        -- ^ list to change
            -> [a]        -- ^ list replaced with maximum element
foldMax :: forall a. Integral a => [a] -> [a]
foldMax [a]
xs = [a]
xs'
  where
    m :: a
m = if [a] -> Bool
forall a. [a] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null [a]
xs then a
0 else [a] -> a
forall a. HasCallStack => [a] -> a
head [a]
xs              -- initial max value
    ([a]
xs', a
largest) = (([a], a) -> a -> ([a], a)) -> ([a], a) -> [a] -> ([a], a)
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl (\([a]
b, a
c) a
a -> (a
largest a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a]
b, a -> a -> a
forall a. Ord a => a -> a -> a
max a
a a
c)) ([], a
m) [a]
xs

-- | Generalise 'repMax' where input is a @Traversable@.
--
-- Seed value from @First@ of @Foldable@.
traverseMax :: (Traversable t, Integral a)
                => t a    -- ^ traversable input
                -> t a    -- ^ modified with maximum element
traverseMax :: forall (t :: * -> *) a. (Traversable t, Integral a) => t a -> t a
traverseMax t a
t = t a
xs'
  where
    m :: a
m = Maybe a -> a
forall a. HasCallStack => Maybe a -> a
fromJust (Maybe a -> a) -> Maybe a -> a
forall a b. (a -> b) -> a -> b
$ First a -> Maybe a
forall a. First a -> Maybe a
getFirst (First a -> Maybe a) -> First a -> Maybe a
forall a b. (a -> b) -> a -> b
$ (a -> First a) -> t a -> First a
forall m a. Monoid m => (a -> m) -> t a -> m
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMap (Maybe a -> First a
forall a. Maybe a -> First a
First (Maybe a -> First a) -> (a -> Maybe a) -> a -> First a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Maybe a
forall a. a -> Maybe a
Just) t a
t
    (a
largest, t a
xs') = (a -> a -> (a, a)) -> a -> t a -> (a, t a)
forall (t :: * -> *) s a b.
Traversable t =>
(s -> a -> (s, b)) -> s -> t a -> (s, t b)
mapAccumR (\a
a a
b -> (a -> a -> a
forall a. Ord a => a -> a -> a
max a
a a
b, a
largest)) a
m t a
t

-- | Generalise 'repMax' where input is a @Traversable@.
--
-- Seed maximum value from head of list or 0 if empty.
traverseMax' :: (Traversable t, Integral a)
                => t a    -- ^ traversable input
                -> t a    -- ^ modified with maximum element
traverseMax' :: forall (t :: * -> *) a. (Traversable t, Integral a) => t a -> t a
traverseMax' t a
t = t a
xs'
  where
    m :: a
m = if t a -> Bool
forall a. t a -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null t a
xs' then a
0 else ([a] -> a
forall a. HasCallStack => [a] -> a
head ([a] -> a) -> (t a -> [a]) -> t a -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. t a -> [a]
forall a. t a -> [a]
forall (t :: * -> *) a. Foldable t => t a -> [a]
toList) t a
t   -- initial max value
    (a
largest, t a
xs') = (a -> a -> (a, a)) -> a -> t a -> (a, t a)
forall (t :: * -> *) s a b.
Traversable t =>
(s -> a -> (s, b)) -> s -> t a -> (s, t b)
mapAccumR (\a
a a
b -> (a -> a -> a
forall a. Ord a => a -> a -> a
max a
a a
b, a
largest)) a
m t a
t