A frequent pattern in my Haskell code is element-wise recursion for transformation of a list with some carried state generated using the data in the list. Usually, this looks something like this:
doSomething :: (SomeA a, SomeB b) => [a] -> [b] doSomething xs = doSomethingWithState xs  where doSomethingWithState  _ =  doSomethingWithState (x:xs) state | someTest x state = someChange x : (doSomethingWithState xs newState) | otherwise = someOtherChange x : (doSomethingWithState xs newState)
For example, say I wanted to count how many of each element appears in a list, turning something like
[1, 3, 3, 3, 4, 7, 7, 8, 8, 9] into
I'd probably do something like the following:
import Data.List import Data.Maybe counts :: (Eq a) => [a] -> [(a, Int)] counts xs = countsWithState xs  where countsWithState  state = state -- End of list, stop here countsWithState (x:xs) state = countsWithState xs $ transformState state x transformState state x -- To get the state... | isNothing $ lookup x state = (x, 1) : state -- Add new elem if new | otherwise = incrElem x state -- Increment elem if not incrElem x  =  -- Should never be reached incrElem x ((index, value):elems) -- Searching through list... | index == x = (index, (value+1)) : elems -- Increment if found | otherwise = (index, value) : incrElem x elems -- Try next if not
In a much simpler but very similar example, if I were trying to keep the running average of all elements in a list, transforming something like
[1, 7, 4, 18, 7, 1, 8, 2, 8, 6, 18, 12] into
[1.0, 4.0, 4.0, 7.5, 7.4, 6.33..., 5.57..., 6.0, 6.22..., 6.2, 7.27..., 7.66...] where every element in the output list is the average of that element and all previous elements in the input list, I might do something like this:
runningAvg :: (Fractional a) => [a] -> [a] runningAvg xs = runningAvgWithState xs 0 1 where runningAvgWithState  _ _ =  runningAvgWithState (x:xs) currentSum currentElems = (currentSum + x) / currentElems : runningAvgWithState xs (currentSum + x) (currentElems + 1)
Notice the pattern is the same. Take a recursive function of a list, define it in terms of a hidden modified version with added state, and with each round transform the state and output computed results as necessary. This pattern emerges all the time in my Haskell code.
Is there a more natural way of implementing this sort of behavior, without a more complicated
xWithState function running the show and adding unnecessary verbosity and complexity?