<div dir="auto">Linear Haskell helps control in-place mutation, but that's still only in mutable references and arrays. As I understand it, data built from regular constructors is more fundamentally immutable because of the way GHC garbage collection works.</div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Sun, Mar 26, 2023, 8:00 PM Viktor Dukhovni <<a href="mailto:ietf-dane@dukhovni.org">ietf-dane@dukhovni.org</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">On Sun, Mar 26, 2023 at 04:24:09PM -0700, Todd Wilson wrote:<br>
<br>
> > Core (with some added comments):<br>
> > -- Unpack the "Ord" dictionary to extract just the required "<="<br>
> > -- function and call the "$wruns" worker ("ww3" is "<=", and "ds"<br>
> > -- is the list to be transformed:<br>
> > --<br>
> > runs :: forall a. Ord a => [a] -> [[a]]<br>
> > runs<br>
> > = \ (@a) ($dOrd :: Ord a) (ds :: [a]) -><br>
> > case $dOrd of { C:Ord ww ww1 ww2 ww3 ww4 ww5 ww6 ww7 -><br>
> > $wruns ww3 ds<br>
> > }<br>
> ><br>
> > Rec {<br>
> > $wruns :: forall {a}. (a -> a -> Bool) -> [a] -> [[a]]<br>
> > $wruns<br>
> > = \ (@a) (ww :: a -> a -> Bool) (ds :: [a]) -><br>
> > case ds of {<br>
> > [] -> []; -- runs [] = []<br>
> > : x xs -> -- runs (x:xs) = let (ys, zs) = run x xs in (x:ys) : runs zs<br>
> > let {<br>
> > ds1 :: ([a], [a]) -- A lazily evaluated thunk for (run x xs)<br>
> > ds1<br>
> > = letrec {<br>
> > -- Internal recursion in "run" returns strict unboxed pairs<br>
> > -- (on the stack) avoiding heap or thunk allocation for the tuple.<br>
> > $wrun :: a -> [a] -> (# [a], [a] #)<br>
> > $wrun<br>
> > = \ (x1 :: a) (ds2 :: [a]) -><br>
> > case ds2 of wild1 { -- (y:ys) is "wild1"<br>
> > [] -> (# [], [] #); -- run x [] = ([], [])<br>
> > : y ys -><br>
> > case ww x1 y of { -- x <= y ?<br>
> > False -> (# [], wild1 #); -- else ([], y:ys)<br>
> > True -> -- then let (us, vs) = run y ys in (y:us, vs)<br>
> > let {<br>
> > ds3 :: ([a], [a]) -- A "thunk" for (run y ys) evaluated lazily<br>
> ><br>
> <br>
> Why doesn't ds3 have an explicitly unboxed pair type, and does that have<br>
> any performance implications? For example, ...<br>
<br>
Precisely because "ds3" must be evaluated lazily, it can't be an unboxed<br>
pair (which are always strictly evaluated).<br>
<br>
> > ds3 = case $wrun y ys of { (# ww1, ww2 #) -> (ww1, ww2) } } in<br>
> > (# : y (case ds3 of { (us, vs) -> us }),<br>
> > case ds3 of { (us, vs) -> vs } #)<br>
<br>
> Granted I'm not that familiar with Core, but It sure looks like this code<br>
> breaks apart pairs (with the equivalent of fst and snd) and rebuilds them<br>
<br>
The inner (recursive) invocation of "run" must also be lazily evaluated,<br>
so yes, its output needs to be boxed as a pair.<br>
<br>
<br>
> > When we do want the successor of the first element, we look no futher<br>
> > than necessary:<br>
> ><br>
> > λ> head $ runs $ 42 : 0 : undefined<br>
> > [42]<br>
> ><br>
> > λ> take 2 $ head $ runs $ 42 : 43 : undefined<br>
> > [42,43]<br>
> ><br>
> > Does this help?<br>
> <br>
> Yes, it does, thanks, although I was aware of this aspect of the laziness<br>
> of my code from the beginning and was concerned more with how the output<br>
> lists were built.<br>
<br>
As with all lists, they are built via the (:) constructor from a head<br>
element and a tail. GHC reuses any full list or tail it can reuse, and<br>
constructs new cons cells that are not already in hand.<br>
<br>
Because these are pure functions working with immutable data, to<br>
construct an initial segment of a list we must build a new list, we<br>
can't truncate the original original in place, it is immutable.<br>
<br>
Therefore, the original list will be picked apart and reassembled.<br>
<br>
With "linear Haskell" there are in some cases opportunities to mutate<br>
certain objects in place, because they are sure to not have any other<br>
references. But that isn't the case here.<br>
<br>
So even `runs [0..10]` has to pick apart and reassemble the list. I<br>
hope I understood correctly what you're getting at with the concern<br>
about building and rebuilding.<br>
<br>
It looks to me like the Core code does exactly as much building and<br>
re-building as required by laziness, and the result can be consumed in a<br>
single pass in constant space (multi-pass use naturally memoises the<br>
result).<br>
<br>
-- <br>
Viktor.<br>
_______________________________________________<br>
Haskell-Cafe mailing list<br>
To (un)subscribe, modify options or view archives go to:<br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe" rel="noreferrer noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe</a><br>
Only members subscribed via the mailman list are allowed to post.</blockquote></div>