content/docs/hoon/reference/stdlib/1b.md · urbit.org

git.iko.soy/urbit.org

on 4fdc19d help sign in

urbit.org/content/docs/hoon/reference/stdlib/1b.md

309 lines 4.9 kB history raw

1+++

2title = "1b: Tree Addressing"

3weight = 2

4template = "doc.html"

5+++

7Check out the Nock [explanation](/docs/nock/) for more

8information on the tree-addressing system.

10## `++cap`

12Tree head

14Tests whether the tree address `a` is in the head or the tail of a [`noun`](/docs/glossary/noun).

15Produces the constant [`atom`](/docs/glossary/atom) `%2` if it is within the head (subtree `+2`), or

16the constant [`atom`](/docs/glossary/atom) `%3` if it is within the tail (subtree `+3`).

18#### Accepts

20`a` is an [`atom`](/docs/glossary/atom).

22#### Produces

24A constant [`atom`](/docs/glossary/atom).

26#### Source

28```hoon

29++ cap

30 ~/ %cap

31 |= a=@

32 ^- ?(%2 %3)

33 ?- a

34 %2 %2

35 %3 %3

36 ?(%0 %1) !!

37 * $(a (div a 2))

38 ==

39```

41#### Examples

43```

44> (cap 4)

45%2

46```

48```

49> (cap 6)

50%3

51```

53```

54> (cap (add 10 9))

55%2

56```

58```

59> (cap 1) ::address '1' is in neither the head nor the tail

60! exit

61```

63```

64> (cap 0x40))

65%2

66> `@`0x40

6764

68```

70```

71> (cap 'a')

72%3

73> `@`'a'

7497

75```

77---

79## `++mas`

81Address within head/tail

83Computes the tree address of [`atom`](/docs/glossary/atom) `a` within either the head (`+2`) or tail

84(`+3`) of a [`noun`](/docs/glossary/noun).

86#### Accepts

88`a` is an [`atom`](/docs/glossary/atom).

90#### Produces

92An [`atom`](/docs/glossary/atom).

94#### Source

96```hoon

97++ mas

98 ~/ %mas

99 |= a=@

100 ^- @

101 ?- a

102 ?(%2 %3) 1

103 ?(%0 %1) !!

104 * (add (mod a 2) (mul $(a (div a 2)) 2))

105 ==

106```

107

108#### Examples

109

110```

111> (mas 3)

1121

113```

114

115```

116> (mas 4)

1172

118```

119

120```

121> (mas 5)

1223

123> (cap 5) ::`(cap a)` computes whether address `a` is in the head or the tail

124%2

125```

126

127```

128> (mas 7)

1293

130> (cap 7)

131%3

132```

133

134```

135> (mas 11)

1367

137```

138

139```

140> (mas (mas 11))

1413

142```

143

144```

145> (cap (mas 6))

146%3

147```

148

149```

150> (mas 0) ::address `0` is in neither the head nor the tail

151! exit

152```

153

154```

155> (mas 1) ::address `1` is in neither the head nor the tail

156! exit

157```

158

159#### Discussion

160

161```

162 1

163 / \

164 / \

165 2 3 <--here are the head (`+2`) and the tail (`+3`)

166 / \ /\

167 4 5 6 7

168 /\ /\ /\ /\

169 (continues...)

170```

171

172Running `(mas 7)` in the [`Dojo`](/docs/glossary/dojo) will return `3`, because address `+3` is what

173`+7` now occupies. The tree below helps illustrate the relationship. With

174parentheses are `a` values (if `a` is in subtree `+3`), and without parentheses

175are the values returned with `(mas a)`.

176

177```

178 1(3) ::new/(old) addresses

179 / \

180 2 3

181 (6) (7)

182 / \ /\

183 / \ / \

184 4 5 6 7

185 (12) (13) (14) (15)

186 / \ / \ / \ / \

187 (continues...)

188```

189

190Notice how the old values in the head (subtree `+2`) were not illustrated in

191this case, because `+7` is within the tail (subtree `+3`).

192

193---

194

195## `++peg`

196

197Address within address

198

199Computes the absolute address of `b`, a relative address within the subtree

200`a`.

201

202#### Accepts

203

204`a` is an [`atom`](/docs/glossary/atom).

205

206`b` is an [`atom`](/docs/glossary/atom).

207

208#### Produces

209

210An [`atom`](/docs/glossary/atom).

211

212#### Source

213

214```hoon

215++ peg

216 ~/ %peg

217 |= [a=@ b=@]

218 ?< =(0 a)

219 ^- @

220 ?- b

221 %1 a

222 %2 (mul a 2)

223 %3 +((mul a 2))

224 * (add (mod b 2) (mul $(b (div b 2)) 2))

225 ==

226```

227

228#### Examples

229

230```

231> (peg 4 1)

2324

233```

234

235```

236> (peg 1 4)

2374

238```

239

240```

241> (peg 4 2)

2428

243```

244

245```

246> (peg 4 8)

24732

248```

249

250```

251> (peg 4 (4 2))

25232

253```

254

255```

256> (peg 8 45)

257269

258```

259

260```

261> (cap (peg 4 2)) ::`(cap a)` computes whether address `a` is in the head or the tail

262%2

263```

264

265#### Discussion

266

267In other words, the subtree at address `a` is treated as a tree in its own

268right (starting with root `+1`, head `+2`, and tail `+3`). Relative address

269`b` is found with respect to `a`, and then its absolute address, within the

270greater tree, is returned.

271

272Running `(peg 3 4)` in the [`Dojo`](/docs/glossary/dojo), for example, will return `12`. Looking at

273a tree diagram makes it easy to see why.

274

275```

276 1

277 / \

278 / \

279 / \

280 2 3 <- here is the subtree `+3`. The subtree address is `a` in `(peg a b)`

281 / \ / \

282 / \ / \

283 4 5 6 7

284 / \ / \ / \ / \

285 8 9 10 11 12 13 14 15

286 /\ /\ /\ /\ /\ /\ /\ /\

287 (continues...)

288```

289

290When we consider subtree at address `+3` by itself, it has relative addresses

291that are structured in the same way as its parent tree's absolute addresses.

292The absolute addresses are given in parentheses in the diagram below.

293Notice how relative address `+4` is at the same position as absolute address

294`+12`.

295

296```

297 1(3) ::new/(old) addresses

298 / \

299 2 3

300 (6) (7)

301 / \ /\

302 / \ / \

303 4 5 6 7

304 (12) (13) (14) (15)

305 / \ / \ / \ / \

306 (continues...)

307```

308

309---