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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.