git.iko.soy/urbit.org
on 4fdc19d help sign in
urbit.org/content/docs/hoon/reference/stdlib/2k.md
456 lines 5.4 kB history raw
1+++
2title = "2k: Queue Logic"
3weight = 14
4template = "doc.html"
5+++
7## `++to`
9Queue operations
11Container arm for queue operation arms. The contained arms inherit `a`, its
12sample queue.
14#### Accepts
16`a` is a tree.
18#### Source
20```hoon
21++ to
22 =| a=(tree) :: (qeu)
23 |@
24```
26#### Discussion
28`tree` is the generic tree-shape mold. Maps, sets, and queues all share that
29shape, but they put their elements in different places and have different
30interfaces. `to` is the interface core for `qeu`; it's not generic across all
31the different containers that use `tree`.
33---
35### `+apt:to`
37Check correctness
39Test whether queue `a` is correctly ordered, producing a flag.
41#### Accepts
43`a` is a `que`.
45#### Produces
47A `?`.
49#### Source
51```hoon
52++ apt
53 |- ^- ?
54 ?~ a &
55 ?& ?~(l.a & ?&((mor n.a n.l.a) $(a l.a)))
56 ?~(r.a & ?&((mor n.a n.r.a) $(a r.a)))
57 ==
58```
60#### Examples
62```
63> =bad `(qeu @ud)`[1 ~ 2 ~ 3 ~ ~]
65> ~(apt to bad)
66%.n
67```
69```
70> =good `(qeu @ud)`(~(gas to `(qeu @ud)`~) ~[1 2 3])
72> ~(apt to good)
73%.y
74```
76---
78### `++bal:to`
80Balance
82Vertically rebalances queue `a`.
84#### Accepts
86`a` is a `qeu`.
88#### Produces
90A `qeu`.
92#### Source
94```hoon
95++ bal
96 |- ^+ a
97 ?~ a ~
98 ?. |(?=(~ l.a) (mor n.a n.l.a))
99 $(a l.a(r $(a a(l r.l.a))))
100 ?. |(?=(~ r.a) (mor n.a n.r.a))
101 $(a r.a(l $(a a(r l.r.a))))
102 a
103```
105#### Examples
107```
108> =a `(qeu @ud)`[1 ~ 2 ~ 3 ~ ~]
109> a
110{1 2 3}
111> `*`a
112[1 0 2 0 3 0 0]
113> ~(apt to a)
114%.n
116> =z `(qeu @ud)`~(bal to a)
117> z
118{1 2 3}
119> `*`z
120[2 [1 0 0] 3 0 0]
121> ~(apt to z)
122%.y
123```
125---
127### `++dep:to`
129Maximum Depth
131Produces the maximum depth of leaves (`r.a` and `l.a`) in queue `a`.
133#### Accepts
135`a` is a queue.
137#### Produces
139An atom.
141#### Source
143```hoon
144++ dep
145 |- ^- @
146 ?~ a 0
147 +((max $(a l.a) $(a r.a)))
148```
150#### Examples
152```
153> =a (~(gas to `(qeu @)`~) `(list @)`[1 2 3 4 5 6 7 ~])
154> ~(dep to a)
157> =a (~(gas to `(qeu @)`~) `(list @)`[1 2 3 4 ~])
158> ~(dep to a)
161> =a (~(gas to `(qeu @)`~) `(list @)`[1 2 ~])
162> ~(dep to a)
165> ~(dep to `(qeu tape)`["a" ~ "b" ~ "c" ~ "d" ~ "e" ~ "f" ~ "g" ~ ~])
168> ~(dep to ~(bal to `(qeu tape)`["a" ~ "b" ~ "c" ~ "d" ~ "e" ~ "f" ~ "g" ~ ~]))
170```
172---
174### `++gas:to`
176Push list
178Push all elements of list `b` into the queue `a`.
180#### Accepts
182`a` is a queue, and is the sample of `+to`.
184`b` is a list.
186#### Produces
188A queue.
190#### Source
192```hoon
193++ gas
194 |= b=(list _?>(?=(^ a) n.a))
195 |- ^+ a
196 ?~(b a $(b t.b, a (put i.b)))
197```
199#### Examples
201```
202> `(qeu)`(~(gas to `(qeu @)`~) [1 2 3 ~])
203{3 2 1}
205> =a (~(gas to `(qeu @)`~) [1 2 3 ~])
206> =b [4 5 6 ~]
207> `(qeu)`(~(gas to a) b)
208{6 5 4 3 2 1}
209```
211---
213### `++get:to`
215Head-tail pair
217Produces the head and tail queue of `a`.
219#### Accepts
221`a` is a queue.
223#### Produces
225A cell of the last element in `a` along with the rest of queue `a`.
227#### Source
229```hoon
230++ get
231 |- ^+ ?>(?=(^ a) [p=n.a q=*(tree _n.a)])
232 ?~ a
233 !!
234 ?~ r.a
235 [n.a l.a]
236 =+ b=$(a r.a)
237 :- p.b
238 ?: |(?=(~ q.b) (mor n.a n.q.b))
239 a(r q.b)
240 a(n n.q.b, l a(r l.q.b), r r.q.b)
241```
243#### Examples
245```
246> =s (~(gas to *(tree @)) `(list @)`~[1 2 3])
247> ~(get to s)
248[n=2 l={3} r={1}]
250> ~(get to ~)
251! exit
252```
254---
256### `++nap:to`
258Remove head
260Removes the head of queue `a`, producing the resulting queue.
262#### Accepts
264`a` is a queue.
266#### Produces
268A queue.
270#### Source
272```hoon
273++ nap
274 ?> ?=(^ a)
275 ?: =(~ l.a) r.a
276 =+ b=get(a l.a)
277 bal(n.a p.b, l.a q.b)
278```
280#### Examples
282```
283> =a (~(gas to `(qeu @)`~) `(list @)`[1 2 3 4 5 6 ~])
284> -.a
285n=6
287> =b ~(nap to a)
288> -.b
289n=2
291> a
292[n=6 l={} r={5 4 3 2 1}]
294> b
295[n=2 l=[n=4 l={5} r={3}] r=[n=1 l={} r={}]]
297> `(qeu)`b
298{5 4 3 2 1}
300> `(qeu)`a
301{6 5 4 3 2 1}
302```
304---
306### `++nip:to`
308Removes the root of queue `a`, producing the resulting queue.
310#### Accepts
312`a` is a queue.
314#### Produces
316A queue.
318#### Source
320```hoon
321++ nip
322 |- ^+ a
323 ?~ a ~
324 ?~ l.a r.a
325 ?~ r.a l.a
326 ?: (mor n.l.a n.r.a)
327 l.a(r $(l.a r.l.a))
328 r.a(l $(r.a l.r.a))
329```
331#### Examples
333```
334> =a (~(gas to `(qeu @)`~) `(list @)`[1 2 3 4 5 6 ~])
335> a
336[n=6 l={} r={5 4 3 2 1}]
338> ~(nip to a)
339[n=2 l=[n=4 l={5} r={3}] r=[n=1 l={} r={}]]
340```
342---
344### `++put:to`
346Insert
348Accept noun `b` and adds to queue `a` as the head, producing the
349resulting queue.
351#### Accepts
353`a` is a queue, and is the sample of `+to`.
355`b` is a noun.
357#### Produces
359A queue.
361#### Source
363```hoon
364++ put
365 |* b=*
366 |- ^+ a
367 ?~ a
368 [b ~ ~]
369 bal(l.a $(a l.a))
370```
372#### Examples
374```
375> =a (~(gas to `(qeu @)`~) `(list @)`[3 1 2 4 5 6 ~])
376> `(qeu)`(~(put to a) 7)
377{7 6 5 4 2 1 3}
378```
380---
382### `++tap:to`
384Queue to list
386Produces queue `a` as a list from front to back.
388#### Accepts
390`a` is a queue.
392#### Produces
394A list.
396#### Source
398```hoon
399++ tap
400 =+ b=`(list _?>(?=(^ a) n.a))`~
401 |- ^+ b
402 =+ 0 :: hack for jet match
403 ?~ a
404 b
405 $(a r.a, b [n.a $(a l.a)])
406```
408#### Examples
410```
411> =a (~(gas to `(qeu @)`~) [3 1 2 4 5 6 ~])
412> `*`a
413[6 0 2 [4 [5 0 0] 0] 1 0 3 0 0]
415> ~(tap to a)
416~[3 1 2 4 5 6]
417```
419---
421### `++top:to`
423Produce head
425Produces the head of queue `a` as a `unit`.
427#### Accepts
429`a` is a queue.
431#### Produces
433A unit.
435#### Source
437```hoon
438++ top
439 |- ^- (unit _?>(?=(^ a) n.a))
440 ?~ a ~
441 ?~(r.a [~ n.a] $(a r.a))
442```
444#### Examples
446```
447> =a (~(gas to `(qeu @)`~) `(list @)`[1 2 3 4 5 6 ~])
448> ~(top to a)
449[~ u=1]
450```
452#### Discussion
454An empty queue has no head.
456---