For what it's worth below an implementation I've started toying with a
while ago. A dictionary here is a boxed pair of lists representing ordered
and uniq keys and values.
regards,
Danil
== Transcript ==
[d1 =: dnew NB. empty dictionary is a pair of empty lists
┌┬┐
│││
└┴┘
(1 2 3) d1 dmap 'one';'two';'three' NB. adding to dictionary x -
keys, y values, by default stores a typed lists when possible
┌─────┬───────────────┐
│1 2 3│┌───┬───┬─────┐│
│ ││one│two│three││
│ │└───┴───┴─────┘│
└─────┴───────────────┘
d1 =: (1 2 3) d1 dmap 'one';'two';'three'
d1 dgetv 2 NB. getting a value
┌───┐
│two│
└───┘
d1 dgetv 3 2 1 NB. or several at once
┌─────┬───┬───┐
│three│two│one│
└─────┴───┴───┘
d1 dgetv 0 NB. if key is absent, that is an index error
|index error
| (keys i.y) {vals['keys vals'=.m
[d2 =: ('ONE';'TWO';'THREE') d1 dmap 1 2 3 NB. adding to a
dictionary is the same dmap typed list is demoted to a boxed list by
necessity
┌─────────────────────┬─────────────────────┐
│┌─┬─┬─┬───┬───┬─────┐│┌───┬───┬─────┬─┬─┬─┐│
││1│2│3│ONE│TWO│THREE│││one│two│three│1│2│3││
│└─┴─┴─┴───┴───┴─────┘│└───┴───┴─────┴─┴─┴─┘│
└─────────────────────┴─────────────────────┘
d2 =: ('ONE';'TWO';'THREE') d1 dmap 1 2 3 NB. now both keys and
vals should be boxed
d2 dgetv 'ONE';1
┌─┬───┐
│1│one│
└─┴───┘
0 d2 dgetv 'NOT PRESENT';'ONE';'TWO' NB. dyadic dgetv to get
a default value x if a key is not there
┌─┬─┬─┐
│0│1│2│
└─┴─┴─┘
d1 dadd d2 NB. combining the two - right keys overwrite left keys
┌─────────────────────┬─────────────────────┐
│┌─┬─┬─┬───┬───┬─────┐│┌───┬───┬─────┬─┬─┬─┐│
││1│2│3│ONE│TWO│THREE│││one│two│three│1│2│3││
│└─┴─┴─┴───┴───┴─────┘│└───┴───┴─────┴─┴─┴─┘│
└─────────────────────┴─────────────────────┘
d1 dadd~ d2 NB. order matters
┌─────────────────────┬─────────────────────┐
│┌───┬───┬─────┬─┬─┬─┐│┌─┬─┬─┬───┬───┬─────┐│
││ONE│TWO│THREE│1│2│3│││1│2│3│one│two│three││
│└───┴───┴─────┴─┴─┴─┘│└─┴─┴─┴───┴───┴─────┘│
└─────────────────────┴─────────────────────┘
d2 dsub d1 NB. subtracting -- left keys removed
┌───────────────┬───────┐
│┌───┬───┬─────┐│┌─┬─┬─┐│
││ONE│TWO│THREE│││1│2│3││
│└───┴───┴─────┘│└─┴─┴─┘│
└───────────────┴───────┘
(1;'THREE') drmk d2 NB. removing keys
┌─────────────┬───────────────┐
│┌─┬─┬───┬───┐│┌───┬─────┬─┬─┐│
││2│3│ONE│TWO│││two│three│1│2││
│└─┴─┴───┴───┘│└───┴─────┴─┴─┘│
└─────────────┴───────────────┘
dkvs d1 NB. keys - values pairs
┌─┬─────┐
│1│one │
├─┼─────┤
│2│two │
├─┼─────┤
│3│three│
└─┴─────┘
((2*[) ; ]) ddokv d1 NB. dkvs above is
implemented as an adverb applying ; between k and v, u could be something
else
┌─┬─────┐
│2│one │
├─┼─────┤
│4│two │
├─┼─────┤
│6│three│
└─┴─────┘
== Implementation ==
samelength =: =&:#
matchitemshape =: -:&:(}.@:$)
joinboxed =: ,&:(boxopen"_1)
coalesce =: joinboxed`(, :: joinboxed)@. matchitemshape
dpack=: 13 : 'x;<y'
dnew =: ''dpack''
dkeys =: 0&{::
dvals =: 1&{::
ddokv =: 1 : 'dkeys (u&[)"_1 dvals'
dkvs =: ; ddokv
dlen =: #@:dkeys
dchk =: ((2=#) *. (dkeys samelength dvals) *. ([:(-:~.)dkeys)) :: 0 NB.
boxed pair of samelength keys and vals, keys uniq
dadd =: 4 : '(dkeys y) x dmap (dvals y)'
dsub =: 4 : '(}:(dkeys y) coalesce {.dkeys x) drmk x'
drmk =: 4 : 0
'keys values' =: y
mask =: -. keys e. x
(mask#keys) dpack (mask#values)
)
drmv =: drmk &.|.
dgetv =: 1 : 0
(keys i. y) { vals [ 'keys vals' =. m
:
(keys i. y) { vals [ vals =. vals coalesce x [ 'keys vals' =. m
)
dmap =: 1 : 0 NB. x are keys, y are vals
:
assert. x samelength y NB. enforce 1:1 mapping between keys and vals
'keys vals' =. m
keys =. keys coalesce x [ vals =. vals coalesce y
revseive =. ~:&.|. keys NB. keys can be not uniq, reverse seive to
'overwrite' by the last key-value pair
(revseive # keys) dpack (revseive # vals)
)
вт, 1 февр. 2022 г. в 16:56, Alex Shroyer <[email protected]>:
> In the past, I have implemented 2-column "pseudo-dictionaries" in J. It
> works, but feels very awkward compared to working with arrays:
> ]d=: (;:'a b c'),.1 2 3;'foo bar';(<;:'x y z')
> ┌─┬───────┐
> │a│1 2 3 │
> ├─┼───────┤
> │b│foo bar│
> ├─┼───────┤
> │c│┌─┬─┬─┐│
> │ ││x│y│z││
> │ │└─┴─┴─┘│
> └─┴───────┘
> get=: {{((<,x) I.@E. {."1 y) { {:"1 y}}
> 'b' get d
> ┌───────┐
> │foo bar│
> └───────┘
>
> What I mean by awkward is not only the verbosity required to implement a
> 'get' verb, but also the extra awkwardness when extending this simple
> dictionary to be more useful:
> When I add a key to d which is an atom (rather than a char array), I need
> to rewrite my get verb.
> Or, if I restrict keys in dictionaries to only symbol values, then it
> becomes more difficult to use real-world data as keys.
>
> I think if J syntax supported this datatype natively, then the above 'get'
> verb would just be
> 'b' { dict
> Which is much better as a tool of thought.
>
>
> To answer Henry's questions:
>
> My definition of a dictionary is:
> A collection where data is organized by key, where keys can be symbols,
> strings, or numbers (or possibly other data types) and values can be
> arbitrary J data.
>
> Essential dictionary operations are:
> - create/read/update/delete by key
> - query if key exists
> - enumerate all keys (returns an array of boxed keys)
> - enumerate all values (returns an array of boxed values)
> - merge two dictionaries e.g. (Z=: X merge Y) and if X and Y share any key,
> then Z gets the key/value pair from Y
>
> Nice features to have, but not necessary:
> - keys are stored in J's sorting order
> - dictionaries can be serialized/deserialized for persistent disk storage
> or for sending to other processes
>
> On Tue, Feb 1, 2022 at 8:37 AM ethiejiesa via Programming <
> [email protected]> wrote:
>
> > Maybe negative anwsers could help clarify things?
> > - Why is a 2-column inverted table, together with appropriate access
> > idioms,
> > not a dictionary?
> > - HPC folk have been representing trees as cleverly-arranged arrays for
> > years,
> > apparently. Why are tries [0] not dictionaries?
> >
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
>
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
