git.iko.soy/urbit.org
on b00decd help sign in
urbit.org/content/docs/hoon/reference/stdlib/2h.md
826 lines 13 kB history raw
1+++
2title = "2h: Set Logic"
3weight = 11
4template = "doc.html"
5+++
7### `++in`
9Set operations
11Core whose arms contain a variety of functions that operate on `set`s. Its
12sample accepts the input `set` to be manipulated.
14#### Accepts
16A `set`.
18#### Source
20```hoon
21 ++ in
22 ~/ %in
23 |_ a=(set)
24```
26#### Examples
28```
29 > ~(. in (sy "asd"))
30 <13.evb [nlr(^$1{@tD $1}) <414.fvk 101.jzo 1.ypj %164>]>
31```
33### `++all:in`
35Logical AND
37Computes the logical AND on every element in `a` slammed with `b`, producing a
38flag.
40#### Accepts
42`a` is a `set`.
44`b` is a wet gate that accepts a noun and produces a flag.
46#### Produces
48A flag.
50#### Source
52```hoon
53 ++ all :: logical AND
54 ~/ %all
55 |* b=$-(* ?)
56 |- ^- ?
57 ?~ a
58 &
59 ?&((b n.a) $(a l.a) $(a r.a))
60```
62#### Examples
64```
65 > =b (sy `(list [@t *])`[['a' 1] ['b' [2 3]] ~])
66 > (~(all in b) |=(a=* ?@(+.a & |)))
67 %.n
69 > =b (sy `(list @t)`['john' 'bonita' 'daniel' 'madeleine' ~])
70 > (~(all in b) |=(a=@t (gte a 100)))
71 %.y
72```
74---
75### `++any:in`
77Logical OR
79Computes the logical OR on every element of `a` slammed with `b`, producing a
80flag.
82#### Accepts
84`a` is a `set`.
86`b` is a gate that accepts a noun and produces a flag.
88#### Produces
90A flag.
92#### Source
94```hoon
95 ++ any :: logical OR
96 ~/ %any
97 |* b=$-(* ?)
98 |- ^- ?
99 ?~ a
100 |
101 ?|((b n.a) $(a l.a) $(a r.a))
102```
104#### Examples
106```
107 > =b (sy `(list [@t *])`[['a' 1] ['b' [2 3]] ~])
108 > (~(any in b) |=(a/* ?@(+.a & |)))
109 %.y
111 > =b (sy `(list @t)`['john' 'bonita' 'daniel' 'madeleine' ~])
112 > (~(any in b) |=(a=@t (lte a 100)))
113 %.n
114```
116---
117### `++apt:in`
119Check correctness
121Computes whether `a` has a correct horizontal order and a correct vertical
122order, producing a flag.
124#### Accepts
126`a` is a set.
128#### Produces
130A flag.
132#### Source
134```hoon
135 ++ apt :: check correctness
136 =< $
137 ~/ %apt
138 =| [l=(unit) r=(unit)]
139 |. ^- ?
140 ?~ a &
141 ?& ?~(l & (gor n.a u.l))
142 ?~(r & (gor u.r n.a))
143 ?~(l.a & ?&((mor n.a n.l.a) $(a l.a, l `n.a)))
144 ?~(r.a & ?&((mor n.a n.r.a) $(a r.a, r `n.a)))
145 ==
146```
148#### Examples
150```
151 > ~(apt in ~)
152 %.y
154 > =a (sy [1 2 3 4 5 6 ~])
155 > a
156 [n=6 l={5 4} r={1 3 2}]
157 > ~(apt in a)
158 %.y
160 > =z ?~ a ~ a(n 7)
161 > z
162 [n=7 l={5 4} r={1 3 2}]
163 > ~(apt in z)
164 %.n
165```
167#### Discussion
169See section [`2f`](/docs/hoon/reference/stdlib/2f) for more information on noun ordering.
171---
172### `++bif:in`
174Bifurcate
176Splits set `a` into two sets `l` and `r`, with any noun `b` removed.
178#### Accepts
180`a` is a set.
182`b` is a noun.
184#### Produces
186A cell of two sets.
188#### Source
190```hoon
191 ++ bif :: splits a by b
192 ~/ %bif
193 |* b=*
194 ^+ [l=a r=a]
195 =< +
196 |- ^+ a
197 ?~ a
198 [b ~ ~]
199 ?: =(b n.a)
200 a
201 ?: (gor b n.a)
202 =+ c=$(a l.a)
203 ?> ?=(^ c)
204 c(r a(l r.c))
205 =+ c=$(a r.a)
206 ?> ?=(^ c)
207 c(l a(r l.c))
208```
210#### Examples
212```
213 > =a (sy `(list @)`[1 2 3 4 5 6 ~])
214 > a
215 [n=6 l={5 4} r={1 3 2}]
217 > (~(bif in a) 6)
218 [l=[n=4 l=[n=5 l={} r={}] r=~] r=[n=2 l=[n=1 l={} r={3}] r=~]]
220 > (~(bif in a) 100)
221 [l=[n=6 l=[n=4 l={5} r={}] r=[n=2 l={1 3} r={}]] r=~]
222```
224---
225### `++del:in`
227Remove noun
229Removes `b` from the `set` `a`.
231#### Accepts
233`a` is a set.
235`b` is a noun.
237#### Produces
239A set.
241#### Source
243```hoon
244 ++ del :: b without any a
245 ~/ %del
246 |* b=*
247 |- ^+ a
248 ?~ a
249 ~
250 ?. =(b n.a)
251 ?: (gor b n.a)
252 a(l $(a l.a))
253 a(r $(a r.a))
254 |- ^- [$?(~ _a)]
255 ?~ l.a r.a
256 ?~ r.a l.a
257 ?: (mor n.l.a n.r.a)
258 l.a(r $(l.a r.l.a))
259 r.a(l $(r.a l.r.a))
260```
263#### Examples
265```
266 > =b (sy `(list @t)`['a' 'b' 'c' ~])
267 > (~(del in b) 'a')
268 [n='b' l=[n='c' l={} r={}] r=~]
270 > =b (sy `(list @t)`['john' 'bonita' 'daniel' 'madeleine' ~])
271 > (~(del in b) 'john')
272 [n='madeleine' l=[n='daniel' l={} r={'bonita'}] r=~]
274 > (~(del in b) 'susan')
275 [n='madeleine' l=[n='daniel' l={} r={'bonita'}] r=[n='john' l={} r={}]]
276```
278---
279### `++dif:in`
281Difference
283Computes the difference between `a` and `b`, producing the set of items in `a`
284that are not in `b`.
286#### Accepts
288`a` is a set.
290`b` is a set.
292#### Produces
294A set.
296#### Source
298```hoon
299 ++ dif :: difference
300 ~/ %dif
301 =+ b=a
302 |@
303 ++ $
304 |- ^+ a
305 ?~ b
306 a
307 =+ c=(bif n.b)
308 ?> ?=(^ c)
309 =+ d=$(a l.c, b l.b)
310 =+ e=$(a r.c, b r.b)
311 |- ^- [$?(~ _a)]
312 ?~ d e
313 ?~ e d
314 ?: (mor n.d n.e)
315 d(r $(d r.d))
316 e(l $(e l.e))
317 --
318```
320#### Examples
322```
323 > =c (sy 1 2 3 ~)
324 > =d (sy 2 3 4 ~)
325 > (~(dif in c) d)
326 [n=1 l=~ r=~]
328 > (~(dif in d) c)
329 [n=4 l=~ r=~]
331 > `(set @ud)`(~(dif in c) d)
332 {1}
334 > `(set @ud)`(~(dif in d) c)
335 {4}
336```
338---
339### `++dig:in`
341Address b in a
343Produce the tree address of `b` within `a`.
345#### Accepts
347`a` is a set.
349`b` is a noun.
351#### Produces
353The `unit` of an atom.
355#### Source
357```hoon
358 ++ dig :: axis of a in b
359 |= b=*
360 =+ c=1
361 |- ^- (unit @)
362 ?~ a ~
363 ?: =(b n.a) [~ u=(peg c 2)]
364 ?: (gor b n.a)
365 $(a l.a, c (peg c 6))
366 $(a r.a, c (peg c 7))
367```
370#### Examples
372```
373 > =a (sy `(list @)`[1 2 3 4 5 6 7 ~])
374 > `(set @)`a
375 {5 4 7 6 1 3 2}
377 > -.a
378 n=6
380 > (~(dig in a) 7)
381 [~ u=12]
383 > (~(dig in a) 2)
384 [~ u=14]
386 > (~(dig in a) 6)
387 [~ u=2]
388```
390#### Discussion
392For more on the tree addressing system, see section [1b](/docs/hoon/reference/stdlib/1b).
394---
395### `++gas:in`
397Concatenate
399Insert the elements of a `list` `b` into a `set` `a`.
401#### Accepts
403`a` is a set.
405`b` is a list.
407#### Produces
409A `set`.
411#### Source
413```hoon
414 ++ gas :: concatenate
415 ~/ %gas
416 |= b=(list _?>(?=(^ a) n.a))
417 |- ^+ a
418 ?~ b
419 a
420 $(b t.b, a (put i.b))
421```
423#### Examples
425```
426 > =b `(set @t)`(sy `(list @t)`['bonita' 'madeleine' 'rudolf' 'john' ~])
427 > b
428 {'bonita' 'madeleine' 'rudolf' 'john'}
430 > (~(gas in b) `(list @t)`['14' 'things' 'number' '1.337' ~])
431 [n='number' l={'1.337' '14'} r={'things' 'bonita' 'madeleine' 'rudolf' 'john'}]
433 > =s (sy `(list @t)`['a' 'b' 'c' 'd' 'e' ~])
434 > (~(gas in s) `(list @t)`['1' '2' '3' ~])
435 [n='e' l=[n='1' l={} r={'3' '2'}] r=[n='b' l={'d' 'a' 'c'} r={}]]
436```
438---
439### `++has:in`
441b in a?
443Checks if `b` is an element of `a`, producing a flag.
445#### Accepts
447`a` is a set.
449`b` is a noun.
451#### Produces
453A flag.
455#### Source
457```hoon
458 ++ has
459 ~/ %has
460 |* b=*
461 ^- ?
462 :: wrap extracted item type in a unit because bunting fails
463 ::
464 :: If we used the real item type of _?^(a n.a !!) as the sample type,
465 :: then hoon would bunt it to create the default sample for the gate.
466 ::
467 :: However, bunting that expression fails if :a is ~. If we wrap it
468 :: in a unit, the bunted unit doesn't include the bunted item type.
469 ::
470 :: This way we can ensure type safety of :b without needing to perform
471 :: this failing bunt. It's a hack.
472 ::
473 %. [~ b]
474 |= b=(unit _?>(?=(^ a) n.a))
475 => .(b ?>(?=(^ b) u.b))
476 |- ^- ?
477 ?~ a
478 |
479 ?: =(b n.a)
480 &
481 ?: (gor b n.a)
482 $(a l.a)
483 $(a r.a)
484```
486#### Examples
488```
489 > =a (~(gas in `(set @t)`~) `(list @t)`['a' 'b' 'c' ~])
490 > (~(has in a) 'a')
491 %.y
493 > (~(has in a) 'z')
494 %.n
495```
497---
498### `++int:in`
500Intersection
502Produces a set of the intersection between two sets of the same type,
503`a` and `b`.
505#### Accepts
507`a` is a set.
509`b` is a set.
511#### Produces
513A `set`.
515#### Source
517```hoon
518 ++ int :: intersection
519 ~/ %int
520 =+ b=a
521 |@
522 ++ $
523 |- ^+ a
524 ?~ b
525 ~
526 ?~ a
527 ~
528 ?. (mor n.a n.b)
529 $(a b, b a)
530 ?: =(n.b n.a)
531 a(l $(a l.a, b l.b), r $(a r.a, b r.b))
532 ?: (gor n.b n.a)
533 %- uni(a $(a l.a, r.b ~)) $(b r.b)
534 %- uni(a $(a r.a, l.b ~)) $(b l.b)
535 --
536```
539#### Examples
541```
542 > (~(int in `(set @t)`(sy "acmo")) `(set @t)`(sy "ham"))
543 [n='m' l={'a'} r={}]
545 > (~(int in (sy "acmo")) ~)
546 ~
548 > (~(int in `(set @t)`(sy "ac")) `(set @t)`(sy "ha"))
549 [n='a' l={} r={}]
550```
552---
553### `++put:in`
555Put b in a
557Add an element `b` to the set `a`, producing a set.
559#### Accepts
561`a` is a set.
563`b` is a noun.
565#### Produces
567A `set`.
569#### Source
571```hoon
572 ++ put :: puts b in a, sorted
573 ~/ %put
574 |* b=*
575 |- ^+ a
576 ?~ a
577 [b ~ ~]
578 ?: =(b n.a)
579 a
580 ?: (gor b n.a)
581 =+ c=$(a l.a)
582 ?> ?=(^ c)
583 ?: (mor n.a n.c)
584 a(l c)
585 c(r a(l r.c))
586 =+ c=$(a r.a)
587 ?> ?=(^ c)
588 ?: (mor n.a n.c)
589 a(r c)
590 c(l a(r l.c))
591```
593#### Examples
595```
596 > =a (~(gas in `(set @t)`~) `(list @t)`['a' 'b' 'c' ~])
597 > =b (~(put in a) 'd')
598 > `(set @t)`b
599 {'d' 'a' 'c' 'b'}
601 > -.l.+.b
602 n='d'
603```
605---
606### `++rep:in`
608Accumulate
610Accumulate the elements of `a` using a gate `b`.
612#### Accepts
614`a` is a `set`.
616`b` is a gate.
618#### Produces
620A noun.
622#### Source
624```hoon
625 ++ rep :: reduce to product
626 ~/ %rep
627 |* b=_=>(~ |=([* *] +<+))
628 |-
629 ?~ a +<+.b
630 $(a r.a, +<+.b $(a l.a, +<+.b (b n.a +<+.b)))
631```
633#### Examples
635```
636 > =a (~(gas in *(set @)) [1 2 3 ~])
637 > `(set @)`a
638 {1 3 2}
640 > (~(rep in a) |=([a=@ b=@] (add a b)))
641 b=6
642```
644---
645### `++run:in`
647Apply gate to set
649Produce a `set` containing the products of gate `b` applied to each element
650in `a`.
652#### Accepts
654`a` is a `set`.
656`b` is a gate.
658#### Produces
660A set.
662#### Source
664```hoon
665 ++ run :: apply gate to values
666 ~/ %run
667 |* b=gate
668 =+ c=`(set _?>(?=(^ a) (b n.a)))`~
669 |- ?~ a c
670 =. c (~(put in c) (b n.a))
671 =. c $(a l.a, c c)
672 $(a r.a, c c)
673```
675#### Examples
677```
678 > =s (sy ~["a" "A" "b" "c"])
679 > `(set tape)`s
680 {"A" "a" "c" "b"}
682 > (~(run in s) cuss)
683 {"A" "C" "B"}
684```
686---
687### `++tap:in`
689Set to list
691Flattens the `set` `a` into a `list`.
693#### Accepts
695`a` is an set.
697#### Produces
699A list.
701#### Source
703```hoon
704 ++ tap :: convert to list
705 =< $
706 ~/ %tap
707 =+ b=`(list _?>(?=(^ a) n.a))`~
708 |. ^+ b
709 ?~ a
710 b
711 $(a r.a, b [n.a $(a l.a)])
712```
715#### Examples
717```
718 > =s (sy `(list @t)`['a' 'b' 'c' 'd' 'e' ~])
719 > s
720 [n='e' l={} r={'d' 'a' 'c' 'b'}]
722 > ~(tap in s)
723 ~['b' 'c' 'a' 'd' 'e']
724```
726---
727### `++uni:in`
729Union
731Produces a set of the union between two sets of the same type, `a` and
732`b`.
734#### Accepts
736`a` is a set.
738`b` is a set.
740#### Produces
742A set.
744#### Source
746```hoon
747 ++ uni :: union
748 ~/ %uni
749 =+ b=a
750 |@
751 ++ $
752 ?: =(a b) a
753 |- ^+ a
754 ?~ b
755 a
756 ?~ a
757 b
758 ?: =(n.b n.a)
759 b(l $(a l.a, b l.b), r $(a r.a, b r.b))
760 ?: (mor n.a n.b)
761 ?: (gor n.b n.a)
762 $(l.a $(a l.a, r.b ~), b r.b)
763 $(r.a $(a r.a, l.b ~), b l.b)
764 ?: (gor n.a n.b)
765 $(l.b $(b l.b, r.a ~), a r.a)
766 $(r.b $(b r.b, l.a ~), a l.a)
767 --
768```
771#### Examples
773```
774 > (~(uni in `(set @t)`(sy "ac")) `(set @)`(sy "ha"))
775 [n='c' l={'a'} r={'h'}]
777 > (~(uni in `(set @t)`(sy "acmo")) ~)
778 [n='c' l={'a'} r={'m' 'o'}]
780 > (~(uni in `(set @t)`(sy "acmo")) `(set @t)`(sy "ham"))
781 [n='c' l={'a'} r={'m' 'o' 'h'}]
783 > (~(uni in `(set @t)`(sy "acmo")) `(set @t)`(sy "lep"))
784 [n='e' l={} r={'a' 'c' 'm' 'l' 'o' 'p'}]
785```
787---
788### `++wyt:in`
790Set size
792Produces the number of elements in set `a` as an atom.
794#### Accepts
796`a` is an set.
798#### Produces
800An atom.
802#### Source
804```hoon
805 ++ wyt :: size of set
806 =< $
807 ~% %wyt + ~
808 |. ^- @
809 ?~(a 0 +((add $(a l.a) $(a r.a))))
810 --
811```
814#### Examples
816```
817 > =a (~(put in (~(put in (sy)) 'a')) 'b')
818 > ~(wyt in a)
819 2
821 > =b (sy `(list @t)`['john' 'bonita' 'daniel' 'madeleine' ~])
822 > ~(wyt in b)
823 4
824```
826---