{- |
Description: Decode a run-length encoded list
Copyright: Copyright (C) 2021 Yoo Chung
License: GPL-3.0-or-later
Maintainer: dev@chungyc.org

Some solutions to "Problems.P12" of Ninety-Nine Haskell "Problems".
-}
module Solutions.P12 (decodeModified, decodeModified') where

import           Problems.Lists

-- | Given a run-length code list generated by 'Problems.P11.encodeModified',
-- construct its uncompressed version.
--
-- Duplicates each element as appropriate and concatenates them together.
decodeModified :: [Encoding a] -> [a]
decodeModified :: forall a. [Encoding a] -> [a]
decodeModified []                  = []
decodeModified (Single a
x : [Encoding a]
xs)     = a
x a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [Encoding a] -> [a]
forall a. [Encoding a] -> [a]
decodeModified [Encoding a]
xs
decodeModified (Multiple Int
n a
x : [Encoding a]
xs) = Int -> a -> [a]
forall a. Int -> a -> [a]
replicate Int
n a
x [a] -> [a] -> [a]
forall a. [a] -> [a] -> [a]
++ [Encoding a] -> [a]
forall a. [Encoding a] -> [a]
decodeModified [Encoding a]
xs

-- | Given a run-length code list generated by 'Problems.P11.encodeModified',
-- construct its uncompressed version.
--
-- Prepend each element as many times as required, starting from the last element
-- prepended to an empty list, and all the way to the first element.
decodeModified' :: [Encoding a] -> [a]
decodeModified' :: forall a. [Encoding a] -> [a]
decodeModified' [Encoding a]
l = [Encoding a] -> [a] -> [a]
forall a. [Encoding a] -> [a] -> [a]
accumulate' [Encoding a]
l []

accumulate' :: [Encoding a] -> [a] -> [a]
accumulate' :: forall a. [Encoding a] -> [a] -> [a]
accumulate' [] [a]
xs     = [a]
xs
accumulate' (Encoding a
x:[Encoding a]
xs) [a]
ys = Encoding a -> [a] -> [a]
forall a. Encoding a -> [a] -> [a]
duplicate' Encoding a
x ([a] -> [a]) -> [a] -> [a]
forall a b. (a -> b) -> a -> b
$ [Encoding a] -> [a] -> [a]
forall a. [Encoding a] -> [a] -> [a]
accumulate' [Encoding a]
xs [a]
ys

duplicate' :: Encoding a -> [a] -> [a]
duplicate' :: forall a. Encoding a -> [a] -> [a]
duplicate' (Single a
x) [a]
xs     = a
x a -> [a] -> [a]
forall a. a -> [a] -> [a]
: [a]
xs
duplicate' (Multiple Int
n a
x) [a]
xs = Int -> a -> [a] -> [a]
forall a. Int -> a -> [a] -> [a]
prepend' Int
n a
x [a]
xs

prepend' :: Int -> a -> [a] -> [a]
prepend' :: forall a. Int -> a -> [a] -> [a]
prepend' Int
0 a
_ [a]
xs = [a]
xs
prepend' Int
n a
x [a]
xs
  | Int
n Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
0 = a
x a -> [a] -> [a]
forall a. a -> [a] -> [a]
: Int -> a -> [a] -> [a]
forall a. Int -> a -> [a] -> [a]
prepend' (Int
nInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1) a
x [a]
xs
  | Bool
otherwise = [a]
forall a. HasCallStack => a
undefined