PLEAC examples - 5. Hashes

5.0. Introduction

People and parts of computer programs interact in all sorts of ways.

Single scalar variables are like hermits, living a solitary existence whose only meaning comes from within the individual.

Arrays are like cults, where multitudes marshal themselves under the name of a charismatic leader.

In the middle lies the comfortable, intimate ground of the one-to-one relationship that is the hash.

5.0.1. Introduction

   # To associate keys with values, PicoLisp uses (besides the built-in database)
   #    1. Symbol properties ('put', 'get', ':' etc.)
   #    2. Association lists ('assoc', 'asoq', 'get')
   #    3. Binary trees ('idx', 'lup')
   # For the examples in this section we use association lists

   : (de Age
      (Nat . 24)
      (Jules . 25)
      (Josh . 17) )
   -> Age

   : Age
   -> ((Nat . 24) (Jules . 25) (Josh . 17))

   : (push 'Age
      (cons 'Nat 24)
      (cons 'Jules 25)
      (cons 'Josh 17) )
   -> (Josh . 17)

   : Age
   -> ((Josh . 17) (Jules . 25) (Nat . 24) (Nat . 24) (Jules . 25) (Josh . 17))

References cons de push

5.1. Adding elements to a Hash

You need to add an entry to a hash.

5.1..1. Example

   : (de FoodColor
      (Apple . "red")
      (Banana . "yellow")
      (Lemon . "yellow")
      (Carrot . "orange") )
   -> FoodColor

   : FoodColor
   -> ((Apple . "red") (Banana . "yellow") (Lemon . "yellow") (Carrot . "orange"))

   # Add an element to the hash

   : (push 'FoodColor '(Raspberry . "pink"))
   -> (Raspberry . "pink")

   : FoodColor
   -> ((Raspberry . "pink") (Apple . "red") (Banana . "yellow") (Lemon . "yellow") (Carrot . "orange"))

   : (prinl "Known foods:")
   : (for F FoodColor (println (car F)))
   Known foods:
   Raspberry
   Apple
   Banana
   Lemon
   Carrot
   -> Carrot

References car de for prinl println push

5.2. Testing for the Presence of a Key in a Hash

You need to know whether a hash has a particular key, regardless of any possible associated value.

5.2.1. Example

   : (de FoodColor
      (Apple . "red")
      (Banana . "yellow")
      (Lemon . "yellow")
      (Carrot . "orange") )
   -> FoodColor

   : FoodColor
   -> ((Apple . "red") (Banana . "yellow") (Lemon . "yellow") (Carrot . "orange"))

   : (for Name '("Banana", "Martini")
      (prinl Name (if (assoc Name FoodColor) " is a food." " is a drink.")) )
   Banana is a food.
   Martini is a drink.
   -> " is a drink."

References assoc de for if prinl

5.3. Deleting from a Hash

You want to remove an entry from a hash so that it doesn't show up with keys, values, or each. If you were using a hash to associate salaries with employees, and an employee resigned, you'd want to remove their entry from the hash.

5.3.1. Example

   : (de FoodColor
      (Apple . "red")
      (Banana . "yellow")
      (Lemon . "yellow")
      (Carrot . "orange") )
   -> FoodColor

   : FoodColor
   -> ((Apple . "red") (Banana . "yellow") (Lemon . "yellow") (Carrot . "orange"))

   : (de printFoods ()
      (prin "Keys: ")
      (apply println (mapcar car FoodColor))
      (prin "Values: ")
      (apply println (mapcar cdr FoodColor)) )
   -> printFoods

   # Current hash values

   : (printFoods)
   Keys: Raspberry Apple Banana Lemon Carrot
   Values: "pink" "red" "yellow" "yellow" "orange"
   -> "orange"

   # Delete the key 'Banana'

   : (del (assoc 'Banana FoodColor) 'FoodColor)
   -> ((Raspberry . "pink") (Apple . "red") (Lemon . "yellow") (Carrot . "orange"))

   # Hash values after deleting the key 'Banana'

   : (printFoods)
   Keys:    Raspberry Apple Lemon 	 Carrot
   Values:  "pink"    "red" "yellow" "orange"
   -> "orange"

References assoc de del

5.4. Traversing a Hash

You want to perform an action on each entry (i.e., each key-value pair) in a hash.

5.4.1. Example 1

   : (de FoodColor
      (Apple . "red")
      (Banana . "yellow")
      (Lemon . "yellow")
      (Carrot . "orange") )
   -> FoodColor

   : FoodColor
   -> ((Apple . "red") (Banana . "yellow") (Lemon . "yellow") (Carrot . "orange"))

   : (for F FoodColor
      (prinl (car F) " is " (cdr F)) )
   Raspberry is pink
   Apple is red
   Lemon is yellow
   Carrot is orange
   -> "orange"

   : (mapc
      '((Food Color) (prinl Food " is " Color))
      (mapcar car FoodColor)
      (mapcar cdr FoodColor) )
   Raspberry is pink
   Apple is red
   Lemon is yellow
   Carrot is orange
   -> "orange"

   : (for F (sort FoodColor)
      (prinl (car F) " is " (cdr F)) )
   Apple is red
   Carrot is orange
   Lemon is yellow
   Raspberry is pink
   -> "pink"

References car cdr de for mapc mapcar prinl sort

5.4.2. Example 2

Create an input file called 'travin':

abc
From: Rory Gallagher
def
From: Jimi Hendrix
ghi
From: Eric Clapton
jkl
From: Rory Gallagher
mno

and then run the following PicoLisp code:

(load "@lib/misc.l")

(in "travin"
   (until (eof)
      (when (match '(~(chop "From: ") @From) (line))
         (accu 'From @From 1) ) ) )

(for Person (sort From)
   (prinl (car Person) ": " (cdr Person)) )

giving this output:

Eric Clapton: 1
Jimi Hendrix: 1
Rory Gallagher: 2
-> 2

References accu car cdr chop eof for in load match prinl sort until when

5.5. Printing a Hash

You want to print a hash in an idiomatic way.

5.5.1. Example

   : (de FoodColor
      (Apple . "red")
      (Banana . "yellow")
      (Lemon . "yellow")
      (Carrot . "orange") )
   -> FoodColor

   : FoodColor
   -> ((Apple . "red") (Banana . "yellow") (Lemon . "yellow") (Carrot . "orange"))

   : (mapc println FoodColor)
   (Apple . "red")
   (Banana . "yellow")
   (Lemon . "yellow")
   (Carrot . "orange")
   -> (Carrot . "orange")

   : (for X FoodColor
      (prinl (car X) " => " (cdr X)) )
   Apple => red
   Banana => yellow
   Lemon => yellow
   Carrot => orange
   -> "orange"

References car cdr de for mapc prinl println

5.6. Retrieving from a Hash in Insertion Order

The keys and each functions give you the hash elements in a strange order, and you want them in the order in which you inserted them.

5.6.1. Example

   : (setq FoodColor NIL)
   -> NIL

   : FoodColor
   -> NIL

   : (queue 'FoodColor (cons 'Banana "Yellow"))
   -> (Banana . "Yellow")

   : FoodColor
   -> ((Banana . "Yellow"))

   : (queue 'FoodColor (cons 'Apple "Green"))
   -> (Apple . "Green")

   : FoodColor
   -> ((Banana . "Yellow") (Apple . "Green"))

   : (queue 'FoodColor (cons 'Lemon "Yellow"))
   -> (Lemon . "Yellow")

   : FoodColor
   -> ((Banana . "Yellow") (Apple . "Green") (Lemon . "Yellow"))

   # In insertion order, the foods are:

   : (for Food FoodColor
       (prinl "   " (car Food)) )
      Banana
      Apple
      Lemon
   -> Lemon

   # Still in insertion order, the foods' colors are:

   : (for Food FoodColor
       (prinl (car Food) " is colored " (cdr Food) ".") )
   Banana is colored Yellow.
   Apple is colored Green.
   Lemon is colored Yellow.
   -> "."

References car cdr cons for prinl queue setq

5.7. Hashes with Multiple Values Per Key

You want to store more than one value for each key.

5.7.1. Example

Create example output similar to the Linux 'who' command called "who-users":

abelson  tty4         2018-06-12 09:53 (:0.0)
coles    tty6         2018-06-12 10:01 (:0.0)
himanshu tty7         2018-06-12 10:33 (:0.0)
abelson  tty8         2018-06-12 10:55 (:0.0)
himanshu pts/0        2018-06-12 11:47 (:0.0)
himanshu pts/1        2018-06-12 12:58 (:0.0)

then execute the following PicoLisp code:

   # Groups the used terminals per user

   : (setq Ttys
       (sort
         (group
           (in "who-users"
             (make
               (while (read)
                 (link (cons @ (read)))
                 (line) ) ) ) ) ) )
   -> ((abelson tty4 tty8) (coles tty6) (himanshu tty7 pts/0 pts/1))

   # Same, but different layout

   : (for U Ttys
       (prin (car U) ": ")
       (apply println (cdr U)) )
   abelson: tty4 tty8
   coles: tty6
   himanshu: tty7 pts/0 pts/1
   -> pts/1

   # Another way

   : (for U Ttys
       (prinl (car U) ": " (length (cdr U)) " ttys.")
       (for Tty (sort (cdr U))
         (prinl "^I" Tty " (owned by " (car U) ")") ) )
   abelson: 2 ttys.
           tty4 (owned by abelson)
           tty8 (owned by abelson)
   coles: 1 ttys.
           tty6 (owned by coles)
   himanshu: 3 ttys.
           pts/0 (owned by himanshu)
           pts/1 (owned by himanshu)
           tty7 (owned by himanshu)
   -> ")"

   # Delete all pts from the output (destructively)

   : (for U Ttys
      (con U (diff (cdr U) '(pts/0 pts/1))) )
   -> (tty7)

   : Ttys
   -> ((abelson tty4 tty8) (coles tty6) (himanshu tty7))

References apply car cdr char con cons diff for group in length line link make prin prinl println read setq sort while

5.8. Inverting a Hash

Hashes map keys to values.

You have a hash and a value for which you want to find the corresponding key.

5.8.1 Example 1

   : (setq
      Surname '((Mickey . Mantle) (Babe . Ruth))
      FirstName (mapcar '((X) (cons (cdr X) (car X))) Surname) )
   -> ((Mantle . Mickey) (Ruth . Babe))

   : (get FirstName 'Mantle)
   -> Mickey

References get setq

5.8.2 Example 2

Create the following script as "hashinv":

#!/usr/bin/picolisp /usr/lib/picolisp/lib.l

(ifn (argv Given)
   (out 2 (prinl "usage: foodfind food_or_color"))

   (de Color
      ("Apple" . "red")
      ("Banana" . "yellow")
      ("Lemon" . "yellow")
      ("Carrot" . "orange") )

   (when (assoc Given Color)
      (prinl Given " is a food with color " (cdr @) ".") )
   (when (find '((X) (= Given (cdr X))) Color)
      (prinl (car @) "  is a food with color " Given ".") ) )

(bye)

then run the script as follows:

chmod 777 hashinv
./hashinv
./hashinv yellow
./hashinv apple
./hasinv Apple

References argv assoc bye car cdr de find ifn out prinl when

5.8.3 Example 3

   : (de FoodColor
      (Apple . "red")
      (Banana . "yellow")
      (Lemon . "yellow")
      (Carrot . "orange") )
   -> FoodColor

   : FoodColor
   -> ((Apple . "red") (Banana . "yellow") (Lemon . "yellow") (Carrot . "orange"))

   : (extract
       '((F) (and (= "yellow" (cdr F)) (car F)))
       FoodColor )
   -> (Banana Lemon)

   : FoodColor
   -> ((Apple . "red") (Banana . "yellow") (Lemon . "yellow") (Carrot . "orange"))

References = and car cdr de extract

5.8.3 Example 4 - the most effective one ...

   : (setq Names
      '( (Mickey . Mantle) (Babe . Ruth) (Alexander . Burger) (John . McCarthy) ) )
   -> ((Mickey . Mantle) (Babe . Ruth) (Alexander . Burger) (John . McCarthy))

   : (rassoc 'Burger Names)
   -> (Alexander . Burger)

References rassoc setq

5.9. Sorting a Hash

You need to work with the elements of a hash in a particular order.

5.9.1. Example

   : (de FoodColor
      (Apple . "red")
      (Banana . "yellow")
      (Lemon . "yellow")
      (Carrot . "orange") )
   -> FoodColor

   : FoodColor
   -> ((Apple . "red") (Banana . "yellow") (Lemon . "yellow") (Carrot . "orange"))

   # Sort by name of Food

   : (setq FoodColor (sort FoodColor))
   -> ((Apple . "red") (Banana . "yellow") (Carrot . "orange") (Lemon . "yellow"))

   : FoodColor
   -> ((Apple . "red") (Banana . "yellow") (Carrot . "orange") (Lemon . "yellow"))

   # Sort by color of food

   : (setq FoodColor (by cdr sort FoodColor))
   -> ((Carrot . "orange") (Apple . "red") (Banana . "yellow") (Lemon . "yellow"))

   : FoodColor
   -> ((Carrot . "orange") (Apple . "red") (Banana . "yellow") (Lemon . "yellow"))

References by cdr de setq sort

5.10. Merging Hashes

You need to make a new hash with the entries of two existing hashes.

5.10.1. Example

   : (de FoodColor
      (Apple . "red")
      (Banana . "yellow")
      (Lemon . "yellow")
      (Carrot . "orange") )
   -> FoodColor

   : FoodColor
   -> ((Apple . "red") (Banana . "yellow") (Lemon . "yellow") (Carrot . "orange"))

   # Create a hash called DrinkColor.
   # Then merge FoodColor + DrinkColor into a new hash called IngestedColor
   : (setq
         DrinkColor '((Galliano . "yellow") ("Mai Tai" . "blue"))
         IngestedColor (append FoodColor DrinkColor) )
   -> ((Apple . "red") (Banana . "yellow") (Lemon . "yellow") (Carrot . "orange") (Galliano . "yellow") ("Mai Tai" . "blue"))

   : FoodColor
   -> ((Apple . "red") (Banana . "yellow") (Lemon . "yellow") (Carrot . "orange"))

   : DrinkColor
   -> ((Galliano . "yellow") ("Mai Tai" . "blue"))

   : IngestedColor
   -> ((Apple . "red") (Banana . "yellow") (Lemon . "yellow") (Carrot . "orange") (Galliano . "yellow") ("Mai Tai" . "blue"))

   # Show unique colors in IngestedColor

   : (setq AllColors (uniq (mapcar cdr IngestedColor)))
   -> ("red" "yellow" "orange" "blue")

References append cdr de mapcar setq uniq

5.11. Finding Common or Different Keys in Two Hashes

You need to find keys in one hash that are present in another hash or keys in one hash that are not present in another.

5.11.1. Example

   : (de FoodColor
      (Apple . "red")
      (Banana . "yellow")
      (Lemon . "yellow")
      (Carrot . "orange") )
   -> FoodColor

   : FoodColor
   -> ((Apple . "red") (Banana . "yellow") (Lemon . "yellow") (Carrot . "orange"))

   # CitrusColor is a hash mapping citrus food name to its color.
   : (de CitrusColor
      (Lemon . "yellow")
      (Orange . "orange")
      (Lime . "green") )
   -> CitrusColor

   # Build a list of non-citrus foods

   : (filter '((F) (not (assoc (car F) CitrusColor))) FoodColor)
   -> ((Apple . "red") (Banana . "yellow") (Carrot . "orange"))

References assoc car de filter not

5.12. Hashing References

When you use keys on a hash whose keys are references, the references that keys returns no longer work.

This situation often arises when you want to cross-reference two different hashes.

5.12.1. Example

   : (setq Files
       (extract
         '((File) (and (info File) (cons File (car @))))
         '("/etc/termcap", "/vmunix", "/bin/cat") ) )
   -> (("/bin/cat" . 35064))

   : (prinl "open files " (glue ", " (mapcar car Files)))
   open files /bin/cat
   -> "/bin/cat"

   : (for F Files
       (prinl (car F) " is " (cdr F) " bytes long.") )
   /bin/cat is 35064 bytes long.
   -> " bytes long."

References and car cdr cons extract for glue info mapcar prinl setq

5.13. Presizing a Hash

You want to preallocate memory for a hash to speed up your program so we won't have to incrementally allocate memory each time a new entry is added to the hash.

Often you know the final size of a hash before you start building it up, and it's possible to use this information to speed up your program.

Note: this has no meaning in PicoLisp. All data structures grow dynamically.

5.14. Finding the Most Common Anything

You have an aggregate data structure, such as an array or a hash.

You want to know how often each element in the array (or key or value in the hash) occurs.

For instance, if your array contains web server transactions, you might want to find the most commonly requested file. If your hash maps usernames to number of logins, you want to find the most common number of logins.

5.14.1. Example

   : (off Count)
   -> NIL

   : (for Element '(a b c b c d)
      (accu 'Count Element 1) )
   -> (d . 1)

   : Count
   -> ((d . 1) (c . 2) (b . 2) (a . 1))

References accu for off

5.15. Representing Relationships Between Data

You want to represent relationships between elements of data - for instance, the mother of relationship in a family tree or parent process for a process table.

This is closely related to representing tables in relational databases (tables represent relationships between information) and to representing computer science graph structures (edges represent relationships between nodes).

5.15.1. Example

   : (de Father
      (Cain . Adam)
      (Abel . Adam)
      (Seth . Adam)
      (Enoch . Cain)
      (Irad . Enoch)
      (Mehujael . Irad)
      (Methusael . Mehujael)
      (Lamech . Methusael)
      (Jubal . Lamech)
      (Tubalcain . Lamech)
      (Enos . Seth) )
   -> Father

   : (de ancestor (Name)
      (while (assoc Name Father)
         (setq Name (cdr @)) )
      Name )  # Always 'Adam'
   -> ancestor

   : (setq Children
      (mapcar
         '((L) (cons (cdar L) (mapcar car L)))
         (by cdr group Father) ) )
   -> ((Adam Cain Abel Seth) (Cain Enoch) (Enoch Irad) (Irad Mehujael) (Mehujael Methusael) (Methusael Lamech) (Lamech Jubal Tubalcain) (Seth Enos))

   : (de children (Name)
      (prinl Name " begat "
         (if (get Children Name)
            (glue ", " @)
            "nobody" ) ) )
   -> children
   : (children 'Adam)
   Adam begat Cain, Abel, Seth
   -> "Cain, Abel, Seth"

   : (children 'Enos)
   Enos begat nobody
   -> "nobody"

References assoc car cdar cdr cons de get glue group if mapcar prinl setq while

5.16. Program: dutree

The dutree program turns the output of du into sorted, indented output.

Note: under Windows WSL the Linux 'du' command misbehaves and thus 'dutree' gives incorrect results.

5.16.1. The program dutree

Create the program 'dutree':

#!/usr/bin/picolisp /usr/lib/picolisp/lib.l
# dutree - print sorted indented rendition of du output

(load "@lib/misc.l")

# Run du, read input, save directories and sizes
(setq *Dirsize  # ((name size kids ..) ..)
   (by length sort
      (in (list 'du (opt))
         (make
            (while (read)
               (skip)
               (link (list (split (line) "/") @)) ) ) ) ) )

# Assign kids
(for D *Dirsize
   (when (assoc (head -1 (car D)) *Dirsize)
      (conc @ (cons (car D))) ) )

(let Root (car *Dirsize)
   # Figure out how much is taken up in each directory
   # that isn't stored in subdirectories.  add a new
   # fake kid called "." containing that much
   (recur (Root)
      (let (Size (cadr Root)  Cursize Size)
         (for Kid (cddr Root)
            (when (assoc Kid *Dirsize)
               (dec 'Cursize (cadr @))
               (recurse @) ) )
         (unless (= Size Cursize)
            (let Dot (append (car Root) '((".")))
               (push '*Dirsize (list Dot Cursize))
               (conc Root (cons Dot)) ) ) ) )
   # Recursively output everything
   (let (Prefix NIL  Width (length (cadr Root)))
      (recur (Root Prefix Width)
         (let Name (last (car Root))
            (prinl Prefix (align Width (cadr Root)) " " Name)
            (let? Kids
               (flip
                  (by cadr sort
                     (mapcar '((K) (assoc K *Dirsize)) (cddr Root)) ) )
               (setq Prefix (pack Prefix (align Width "|")))
               (setq Width (+ 1 (length Name) (length (cadar Kids))))
               (for Kid Kids
                  (recurse Kid Prefix Width) ) ) ) ) ) )

(bye)

then run Linux commands:

chmod 777 dutree
./dutree
./dutree /usr
./dutree -a
./dutree -a /bin

References + = align append assoc by bye cadar cadr car cddr conc cons dec flip for head in last length let line link list load make mapcar opt pack prinl push read recur recurse setq skip sort split unless when while

http://picolisp.com/wiki/?pcepleachashes

23jun18

ArievW