<div dir="ltr"><div>Thanks, Viktor, for that information, especially the macro for getting Haskel core output at the end, which I will try to use in the future and perhaps avoid having to query this list to get such answers! I have a few follow-up questions on this code, however:</div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Sun, Mar 26, 2023 at 12:07 PM Viktor Dukhovni <<a href="mailto:ietf-dane@dukhovni.org">ietf-dane@dukhovni.org</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">I don't know whether looking at the GHC-generated "Core" for your<br>
implementation will answer any of your questions, but here it is:<br>
<br>
Haskell:<br>
runs (x:xs) = let (ys, zs) = run x xs in (x:ys) : runs zs<br>
where<br>
run x [] = ([], [])<br>
run x (y:ys) = if x <= y<br>
then let (us, vs) = run y ys<br>
in (y:us, vs)<br>
else ([], y:ys)<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></blockquote><div><br></div><div>Why doesn't ds3 have an explicitly unboxed pair type, and does that have any performance implications? For example, ...</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
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></blockquote><div><br></div><div>Granted I'm not that familiar with core, but It sure looks like this code breaks apart pairs (with the equivalent of fst and snd) and rebuilds them</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
}<br>
}; } in<br>
case $wrun x xs of { (# ww1, ww2 #) -> (ww1, ww2) } } in<br>
: (: x (case ds1 of { (ys, zs) -> ys }))<br>
(case ds1 of { (ys, zs) -> $wruns ww zs })<br>
}<br>
end Rec }<br>
<br>
So for a non-empty cons-cell (: x ...) the result is a new cons cell:<br>
<br>
: (x : (fst ds1)) (runs (snd ds1))<br>
--------- --------------<br>
<br>
in which both underline parts are computed lazily (on demand) from the<br>
thunk "ds1":<br>
<br>
λ> head $ head $ runs $ 42 : undefined<br>
42<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? </blockquote><div><br></div><div>Yes, it does, thanks, although I was aware of this aspect of the laziness of my code from the beginning and was concerned more with how the output lists were built. </div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"> FWIW, the (simplified) Core output was generated via:<br>
hscore() {<br>
ghc -ddump-simpl -dsuppress-idinfo -dsuppress-coercions -dsuppress-type-applications -dsuppress-uniques -dsuppress-module-prefixes "$@"<br>
}<br>
hscore -O2 Runs.hs > Runs.core<br></blockquote><div><br></div><div>Thanks again for this, it will be helpful going forward.</div><div><br></div><div>--Todd</div></div></div>