(Will be streamed today, 2023-12-20, at 1930 UTC, and it will be an episode with extended length.)
I wondered: the naive implementation of normalization (make the sum 1) is
normalize :: (Fractional t, Traversable f) => f t -> f t
normalize xs = let total = sum xs in fmap (/total) xs
For f = []
this means that in order to produce the first element, the entire list xs
must have been traversed once (to compute total
) but then the list of normalized values can be produced lazily on-demand.
One can use ArrowLoop
to define the circular version:
import Control.Arrow (loop)
worker :: Fractional t => ([t],t) -> ([t],t)
worker ([],_) = ([],0)
worker (x:xs,total) = let
(xs',total') = worker (xs,total)
in (x/total : xs', x + total')
normalize = loop worker
I expected that the result of this normalize
is a full spine of thunks of the form x/total
but at least ghci :print
tells me otherwise. So does circular programming give no advantage in this case?
What do you mean with “the result”? The result is a single thunk at first and a full list of fractional numbers if fully forced. I’m guessing you mean somewhere in between, but I’m not sure what you mean.
For example I can do this in GHCi:
ghci> xs = [1.0.. 3.0 :: Double]
ghci> ys = normalize xs
ghci> seq (head ys) ()
ghci> :sprint ys
ys = 0.16666666666666666 : _
So it does produce the final list on-demand. But of course a two-pass algorithm would do the same, so what are we trying to show?
Of course both algorithms produce a single thunk at first. As you showed, the interesting moment is when one has demanded the head of the list. My expectation was that since the circular algorithm builds the (spine of) the result list alongside the total, the normalized list would look like
0.16666 : thunk1 : thunk2 : []
But apparently in the worker function, the first component of the result is produced lazily, despite being strict in the first component of the argument .
I think this is actually an issue with :sprint
in GHCi. For example I can change the worker to this:
worker :: ([Double],Double) -> ([Double],Double)
worker ([],_) = ([],0)
worker (x:xs,total) = let
!(!xs',!total') = worker (xs,total)
!xs'' = trace "foo" $ x / total : xs'
!total'' = x + total'
in (xs'', total'')
And then in GHCi:
ghci> xs = [1..3 :: Double]
ghci> ys = normalize xs
ghci> head ys
foo
foo
foo
0.16666666666666666
ghci> :sprint ys
ys = 0.16666666666666666 : _
From the three foo
s you can see that it does force that xs''
thunk three times, but for some reason :sprint
does not see that.
There are some known issues with :sprint
and it is not really meant to be authoritative (e.g. #23902).