4
$\begingroup$

Following up on question Side-effecting an array in an association? and @Mr.Wizard's answer in there, I'm modernizing and tweaking Daniel Lichtblau's efficient queues and ran into a little roadblock.

First, I came up with the following API, stripped-down for brevity. The queue I want is fixed-length and lossy. Make a new queue with newQ[capacity]. Push values to the back with pushQ[aQueue, aValue]; pop values from the front with popQ[aQueue], just like a queue of humans. If the queue is full, just pop the value at the front, losing it (on purpose)

I want pushQ to return the queue it receives, so that I can fold it and chain it as follows:

Fold[pushQ, newQ[4], Range[10]]

Here's what I came up with, with the functional mojo highlighted:

ClearAll[newQ, emptyQQ, fullQQ, pushQ, popQ, peekQ, bumpQ]; 
newQ[cap_Integer] /; cap > 0 :=
  <|"storage" -> ConstantArray[Null, cap],
   "len"    -> 0, "cap"   -> cap,
   "iFront" -> 1, "iBack" -> 1|>;
emptyQQ[Q_] := Q[["len"]] === 0;
fullQQ[Q_]  := Q[["len"]] === Q[["cap"]];
peekQ[Q_]   := Q[["storage", Q[["iFront"]]]];
SetAttributes[bumpQ, HoldFirst];
bumpQ[Q_, index_] := Q[[index]] = Mod[Q[[index]] + 1, Q[["cap"]], 1];
SetAttributes[pushQ, HoldFirst];
pushQ[Q_, item_] :=
  (Q[["storage", Q[["iBack"]]]] = item;
   bumpQ[Q, "iBack"];
   If[fullQQ[Q],
    (*then*)bumpQ[Q, "iFront"],
    (*else*)Q[["len"]]++];
   Q); (* <<<<<<< HERE IS THE FUNCTIONAL MOJO <<<<<<<< *)
SetAttributes[popQ, HoldFirst];
popQ[Q_] /; emptyQQ[Q] := Null;
popQ[Q_] :=
 (Q[["len"]]--;
  With[ {result = Q[["storage", Q[["iFront"]]]]},
   Q[["storage", Q[["iFront"]]]] = Null;
   bumpQ[Q, "iFront"];
   result ])

This passes a bunch of unit tests:

$q = newQ[4];
pushQ[$q, 1]; $q["storage"]
{1, Null, Null, Null}
pushQ[$q, 2]; $q["storage"]
{1, 2, Null, Null}
pushQ[$q, 3]; $q["storage"]
{1, 2, 3, Null}
popQ[$q]
1
$q["storage"]
{Null, 2, 3, Null}
popQ[$q]; $q["storage"]
{Null, Null, 3, Null}
pushQ[$q, 4]; $q["storage"]
{Null, Null, 3, 4}
pushQ[$q, 5]; $q["storage"]
{5, Null, 3, 4}
popQ[$q]
3
$q["storage"]
{5, Null, Null, 4}
pushQ[$q, 6]; pushQ[$q, 7]; pushQ[$q, 8]; pushQ[$q, 9]; pushQ[$q, 10];
$q["storage"]
{9, 10, 7, 8}
popQ[$q]
7

and so on. Now, when I try the obvious generalization to folding, I'm back where I started with the ... in the part assignment is not a symbol.

Fold[pushQ, newQ[4], Range[1]]
During evaluation of In[49]:= Set::setps: <|storage->{Null,Null,Null,Null},len->0,cap->4,iFront->1,iBack->1|> in the part assignment is not a symbol. >>
During evaluation of In[49]:= Set::setps: <|storage->{Null,Null,Null,Null},len->0,cap->4,iFront->1,iBack->1|> in the part assignment is not a symbol. >>
During evaluation of In[49]:= General::stop: Further output of Set::setps will be suppressed during this calculation. >>
<|"storage" -> {Null, Null, Null, Null}, "len" -> 0, "cap" -> 4, "iFront" -> 1, "iBack" -> 1|>

Ok, I need some kind of symbol for Set to work. A couple more attempts as follows produce the same results, and I did a bunch of tracing and printing, and couldn't see a good way through this:

Module[{$q = newQ[4]}, Fold[pushQ, $q, Range[1]]]
During evaluation of In[48]:= Set::setps: <|storage->{Null,Null,Null,Null},len->0,cap->4,iFront->1,iBack->1|> in the part assignment is not a symbol. >>
Module[{$q = newQ[4]}, Fold[($q = pushQ[#1, #2]) &, $q, Range[1]]]
During evaluation of In[44]:= Set::setps: <|storage->{Null,Null,Null,Null},len->0,cap->4,iFront->1,iBack->1|> in the part assignment is not a symbol. >>

EDIT:

This question is really about elegance because I can get meaningful, useful side effects with Map and Scan, as follows:

Module[{q = newQ[4]}, pushQ[q, #] & /@ Range[10]]
{<|"storage" -> {1, Null, Null, Null}, "len" -> 1, "cap" -> 4, "iFront" -> 1, "iBack" -> 2|>, 
   <|"storage" -> {1, 2, Null, Null}, "len" -> 2, "cap" -> 4, "iFront" -> 1, "iBack" -> 3|>, 
   <|"storage" -> {1, 2, 3, Null}, "len" -> 3, "cap" -> 4, "iFront" -> 1, "iBack" -> 4|>, 
   <|"storage" -> {1, 2, 3, 4}, "len" -> 4, "cap" -> 4, "iFront" -> 1, "iBack" -> 1|>,
   <|"storage" -> {5, 2, 3, 4}, "len" -> 4, "cap" -> 4, "iFront" -> 2, "iBack" -> 2|>,
   <|"storage" -> {5, 6, 3, 4}, "len" -> 4, "cap" -> 4, "iFront" -> 3, "iBack" -> 3|>, 
   <|"storage" -> {5, 6, 7, 4}, "len" -> 4, "cap" -> 4, "iFront" -> 4, "iBack" -> 4|>,
   <|"storage" -> {5, 6, 7, 8}, "len" -> 4, "cap" -> 4, "iFront" -> 1, "iBack" -> 1|>,
   <|"storage" -> {9, 6, 7, 8}, "len" -> 4, "cap" -> 4, "iFront" -> 2, "iBack" -> 2|>,
   <|"storage" -> {9, 10, 7, 8}, "len" -> 4, "cap" -> 4, "iFront" -> 3, "iBack" -> 3|>}
$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.