Structure for pairs in Racket

Question

I have following data of children with their father's names:

sally, THOMAS
alfred, JOHNSON
peter, SIMON
dick, THOMAS
harry, JOHNSON
eliz, SIMON

I want to have a function which finds sibling of a particular child. For example (sibling "harry") should return "alfred". Which structure in Racket is best suited for this? Should I use lists, vectors or hash-tables or dictionaries? Thanks for your comments.

Edit: I have created stuctures and its function as suggested by @soegaard :

(struct family (child father) #:transparent)
(define datalist (list  (family 'sally 'THOMAS) (family 'alfred 'JOHNSON) 
   (family 'peter 'SIMON) (family 'dick 'THOMAS) 
   (family 'harry 'JOHNSON) (family 'eliz 'SIMON)))

(define (siblings child_name lst)
  (define outl (for/list ((item lst)
    #:when (equal? (family-child item) child_name)) item))
  (for/list ((item lst)
    #:when (and (equal? (family-father item) (family-father (list-ref outl 0)))
                (not (equal? (family-child item) child_name))))
    (family-child item)  ))    

(siblings 'harry datalist)

It works. The output is:

'(alfred)

Is there a better way?

Edit2: Using findf as suggested by @soegaard (also map and filter instead of for/list):

(define (siblings child_name lst)
  (define fam (findf (lambda (x) (equal? (family-child x) child_name)) lst ))
  (map (lambda (x) (family-child x))
       (filter (lambda (x) (and (equal? (family-father x) (family-father fam))
                                (not (equal? (family-child x) child_name))))
               lst)) )

(siblings 'harry datalist)

It works:

'(alfred)

Answer 1

Your solution is O(n) and works well. I create about a 3 million family objects in my test and your procedure produces an answer in between one and two seconds.

As I mention in my comment you can make it O(1) by using a hash. It supports any data structure and works as indexes. The value can be a node in a tree. Since I'm lazy I kept your structure and made two lookups. One from child to family and one from father to list of family.

#!racket
(define +fathers+ 1000000)
(define +search-average+ (format "Son-1-of-Father-~a" (quotient +fathers+ 2)))
(define +sons+ 3)

(struct family (child father) #:transparent)
(define family-by-child (make-hash))
(define family-by-father (make-hash))
(define datalist
  ;; make a few son father relationships
  (foldl (λ (father relations)
           (let loop ((n +sons+) (acc relations))
             (if (zero? n)
                 acc
                 (loop (sub1 n)
                       (let* ((son (format "Son-~a-of-~a" n father))
                              (fam (family son father)))
                         ;; These two updates the two indexes to do O(1) lookup on both
                         (hash-set! family-by-child son fam)
                         (hash-update! family-by-father
                                       father
                                       (lambda (old) (cons fam old))
                                       '())
                         (cons fam acc))))))
         '()
         ;; make a list of fathers
         (let loop ((n +fathers+) (acc '()))
           (if (zero? n)
               acc
               (loop (sub1 n)
                     (cons (format "Father-~a" n) acc))))))


;; This uses over one second on my machine, grows linear with number of objects
;; note that you need to copy in siblings definition from your question
(time (siblings +search-average+ datalist))

;; My implementation using O(1) hash lookup 
(define (hsiblings child-name)
  (define f (hash-ref family-by-child child-name #f))
  (define families (hash-ref family-by-father (family-father f) '()))
  (map family-child (filter (λ (e) (not (eq? f e))) families)))

;; This produces immediate results no matter the size
(time (hsiblings +search-average+))

Now you could still keep it functional by using immutable hashes. Then it becomes O(log n) since immutable hashes uses trees.

Answer 2

(define data '((sally THOMAS) (alfred JOHNSON) (peter SIMON) 
               (dick THOMAS) (harry JOHNSON) (eliz SIMON)))

(define (siblings child data)
  (define father (second (assq child data)))
  (map first
       (filter (lambda (e)
                 (and (eq? (second e) father)
                      (not (eq? (first e) child))))
               data)))

Testing

> (siblings 'harry data)
'(alfred)

EDIT 1

If you use structs as in your updated question, this becomes:

(define (siblings child data)
  (define father (family-father (findf (lambda (e) (eq? (family-child e) child)) data)))
  (map family-child
       (filter (lambda (e)
                 (and (eq? (family-father e) father)
                      (not (eq? (family-child e) child))))
               data)))

EDIT 2

or, if you want something more rackety:

(define (siblings child data)
  (define father (family-father (findf (lambda (e) (eq? (family-child e) child)) data)))
  (for/fold ((res null)) ((e (in-list data)))
    (define this-child (family-child e))
    (if (and (eq? (family-father e) father) (not (eq? this-child child)))
        (cons this-child res)
        res)))

Note: In this case you have to reverse the result if you want the child names to appear in the same order as in your initial data.

Answer 3

Not very pretty, but use only built in functions. As a data structure I've used a simply list of pairs.

(define (siblings x)
  (define tmp1
    (second (first (memf (lambda (arg)
                           (eq? (first arg) x))
                         lst))))
  (define tmp2 (filter (lambda (ar) (eq? (second ar) tmp1)) lst))
  (define tmp3 (filter (lambda (ar) (not (eq? (first ar) x))) tmp2))
  (map (lambda (ar) (first ar)) tmp3))

Sample data:

(define lst
  (list '("zosia" "Thomas")
        '("sally" "Thomas")
        '("sophie" "Thomas")
        '("magdalena" "Kazimierz")))

The first define (tmp1) in the function gives a name of the x's father, the second filter pairs and leave only those whose father is x's father, the third eliminates pair with x, and finally function returns lists of siblings of the given argument.

Answer 4

Use structures. Try this:

   (struct person (first last) #:transparent)
   (define john (person "John" "Doe"))
   john
   (person-first john)
   (person-last john)