(Will be streamed today, 2023-12-20, at 1930 UTC, and it will be an episode with extended length.)
4 Likes
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 foos 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).