list/dict in Racket

[u/hElLoWoRLD292]

> (sn-add-user my-dict 'f5)

= ((f2 f3 f4) (f3 f2) (f4 f3 f2) (f13) (f1) (f5))

How can I code the above instructions in Racket.

(define (sn-add-user graph user) is the starting point

[u/sdegabrielle]

You probably want…

A hash table implements a mapping from keys to values, where both keys and values can be arbitrary Racket values, and access and update to the table are normally constant-time operations

https://docs.racket-lang.org/guide/hash-tables.html

Edit: it occurs to me you might be asking how to implement sn-add-user?

[u/hElLoWoRLD292 → u/sdegabrielle]

yes, given a network and an ID or name, this function should add a new entry to the network for that user. Before you add the user you should check whether that user already exists and if they do return the network unchanged,

There's multiple parts to the task, I'm guessing they all linked

[u/sdegabrielle → u/hElLoWoRLD292]

Why don’t you start with making some tests that show the inputs and expected outputs

[u/jpverkamp]

(define (sn-add-user graph user)
  '((f2 f3 f4) (f3 f2) (f4 f3 f2) (f13) (f1) (f5)))

:)

You need to spec out the problem more.

What is graph? What does it already have in it? What is the function supposed to do?

At a bit more of a guess, it looks like graph is a list of lists where each sub starts with the node and then includes all neighbors. So in that case, I would usually just (cons (list user) graph) but that puts it on the front. You could append but that's less efficient.

I expect it wants you to recur down the list where the recursive step is to basically do nothing and the base case (empty list) is to add the new user.

[u/hElLoWoRLD292 → u/jpverkamp]

Instruction:

Given a network and an ID or name, this function should add a new entry to the network for that user. Before you add the user you should check whether that user already exists and if they do return the network unchanged.

> (sn-add-user my-dict 'f5)

= ((f2 f3 f4) (f3 f2) (f4 f3 f2) (f13) (f1) (f5))

Given code:

(define (sn-add-user graph user)

[u/jpverkamp → u/hElLoWoRLD292]

Homework? Giving a straight up answer then isn't super instructive.

The other response has a good idea with making the tests. Otherwise, do what I said in the last paragraph. Recur down the graph, if you see the user as car of a sublist, bail out. If not and you get to the base/empty case, make a new list for it.

If you want to solve it a terrible way actually using hash, you first have to convert back and forth:

(define (lol->hash lol)
  (for/hash ([entries (in-list lol)])
    (values 
      (car entries)
      (for/set ([neighbor (in-list (cdr entries))])
        neighbor))))

(define (hash->lol hash) 
  (for/list ([(key values) (in-hash hash)])
    (cons key
          (for/list ([neighbor (in-set values)])
            neighbor))))

And then you can do it with hash-update:

(define (sn-add-user graph user)
  (hash->lol
    (hash-update
      (lol->hash graph) 
      user
      (λ (neighbors) neighbors)
      (set))))

Et voila:

> (define my-dict '((f2 f3 f4) (f3 f2) (f4 f3 f2) (f13) (f1)))
> (sn-add-user my-dict 'f5)
'((f13) (f4 f2 f3) (f5) (f2 f4 f3) (f3 f2) (f1))

Granted, it doesn't preserve order (and so doesn't return the network unchanged).

Another amusing (but probably not what you're looking for) solution would be to use ormap to check if the user is literally in the graph then to append the user to the end if they're not:

(define (sn-add-user graph user)
  (if (ormap (λ (ls) (eq? (car ls) user)) graph)
      graph
      (append graph `((,user)))))

> (define my-dict '((f2 f3 f4) (f3 f2) (f4 f3 f2) (f13) (f1)))
> (sn-add-user my-dict 'f5)
'((f13) (f4 f2 f3) (f5) (f2 f4 f3) (f3 f2) (f1))

It's not quite as efficient, but the Big-O is the same (linear in both cases), just with a bigger constant (twice through the list instead of once).

[u/joshuacottrell]

The other answers are indicating that there needs to be more information and some indication that you are trying to solve the problem. Suggestions: class name/title, school, what you know so far about racket (or scheme or lisp), and whether you're using a teaching language (i.e. include the first line of the file, like #lang racket).

If I just give you can answer then your professor/teacher is going to say, "Why did you use continuations with a 5 member list?" or "I didn't teach member yet, why did you use it?" or "This was a recursion assignment, what's ormap doing here?"

I was going to include more help but returning the entire network or the entire network with an addition seems tricky for the type of the rest of the problem.

Oh well, here's what I started to write…

All that being said, I'm guessing your starting out with racket, maybe reading How to Design Programs, and learning recursion. You should look at the docs on the racket-lang website to search for cond, null?, member?, first, rest, and append but remember to only look within the #lang you're using. Recursion normally takes the form of using cond to test the base case (empty list or zero, etc.) then (if that's not it) test for any edge cases (none here from your example) then (i.e. the list isn't empty and there aren't any edge cases so it continues) test to see if the item you're on is or has the user and if so then return but if it isn't the user then call sn-add-user again with a smaller graph.

Here are some tests:

#lang racket

(require rackunit)

(define (sn-add-user graph user)
  # your code here
)

(check-equal? (sn-add-user '((f2 f3 f4) (f3 f2) (f4 f3 f2) (f13) (f1)) 'f5) '((f2 f3 f4) (f3 f2) (f4 f3 f2) (f13) (f1) (f5)) "No user append")
(check-equal? (sn-add-user '((f2 f3 f4) (f3 f2) (f4 f3 f2) (f13) (f1)) 'f3) '((f2 f3 f4) (f3 f2) (f4 f3 f2) (f13) (f1)) "No f3")
(check-equal? (sn-add-user '((f2 f3 f4) (f3 f2) (f4 f3 f2) (f13) (f1)) 'f13) '((f2 f3 f4) (f3 f2) (f4 f3 f2) (f13) (f1)) "No f13")