[racket] doubly linked list lib

[Laurent]

Hi,

It seems highly probable that there exists a doubly linked list library somewhere, but I couldn't find any.
Does anyone know about something like that or should I make my own? (or is there something obvious that I completely miss?)

Thanks,
Laurent

[Neil Toronto]

Nothing obvious, no. But Racket is designed to encourage programming
without mutation, and doubly linked lists require mutation.

It's very likely a zipper will do what you want. A zipper is much easier
to implement than a doubly linked list, and has similar performance and
uses.

Here's a quick implementation:

#lang racket

(struct zipper (head current tail) #:transparent)

(define (zipper-next z)
(match-define (zipper h c t) z)
(zipper (cons c h) (first t) (rest t)))

(define (zipper-prev z)
(match-define (zipper h c t) z)
(zipper (rest h) (first h) (cons c t)))

(define (zipper-set z new-current)
(match-define (zipper h _ t) z)
(zipper h new-current t))

(define (list->zipper lst)
(zipper empty (first lst) (rest lst)))

(define (zipper->list z)
(match-define (zipper h c t) z)
(append (reverse h) (list c) t))

; tests: replace 2 and 3 with 20 and 30
(define z1 (list->zipper '(1 2 3 4)))
(define z2 (zipper-next z1))
(define z3 (zipper-set z2 20))
(define z4 (zipper-next z3))
(define z5 (zipper-next z4))
(define z6 (zipper-prev z5))
(define z7 (zipper-set z6 30))

(zipper->list z7)
(zipper->list z3) ; just the 2 is different

A zipper is like a cursor. It has a current element, the stuff before
the current element (head), and the stuff after (tail). There are
functions to move forward (zipper-next) and back (zipper-prev). Both
return a new zipper, with a different current element.

The only tricky part is that the head is stored in reverse order to make
it easier to grab the "last" element in the head in zipper-prev. In
reverse order, the "last" element is the first.

Neil T

_________________________________________________
For list-related administrative tasks:
http://lists.racket-lang.org/listinfo/users

[Danny Yoo]

> Nothing obvious, no. But Racket is designed to encourage programming without
> mutation, and doubly linked lists require mutation.
>
> It's very likely a zipper will do what you want. A zipper is much easier to
> implement than a doubly linked list, and has similar performance and uses.

To supplement, here are very old notes I wrote to myself on the kind
of list zipper that Neil is presenting:

https://hkn.eecs.berkeley.edu/~dyoo/plt/zippers.txt

[Laurent]

Thank you very much for this nice intermediate solution, though I need constant-time append, split, insert, remove, + pointers to items, etc. Mutation does seem unavoidable, right.
I started my own lib, but if something already exists, I'm still interested.

The purpose is to make a hash with bounded memory, with replacement of oldest items, or barely used items, or some other replacement criterion.

The final purpose is to make a memoization form with bounded memory, or growing memory but with frequent removal of selected items. If I have time to get there.

I'll keep the zipper in mind for other purposes though!

Laurent

[Stephen Bloch]

On Aug 30, 2011, at 3:18 AM, Laurent wrote:

Thank you very much for this nice intermediate solution, though I need constant-time append, split, insert, remove, + pointers to items, etc. Mutation does seem unavoidable, right.

The "zipper" structure Neil posted has constant-time append if you're already at the head of one zipper and the tail of the other, but in general it'll be linear time.  It has constant-time split, insert, and remove.  What do you mean by "pointers to items" -- that is, what do you need to DO with pointers to items?

Stephen Bloch

sbl...@adelphi.edu

[Jos Koot]

You are stating: hash with bounded memory

Does that mean you will have a limit on the number of entries?

In that case a vector plus a current index might do, I think.

Gives you O(1) access to every element.

If the required number of elements may vary very much, a vector probably is not a good idea, unless using resizable vectors, but that makes some operations O(n).

 

BTW, I like the two posts of  Neil Toronto and Danny Yoo.

 

Jos

---

From: users-...@racket-lang.org [mailto:users-...@racket-lang.org] On Behalf Of Laurent
Sent: martes, 30 de agosto de 2011 9:18
To: Danny Yoo
Cc: us...@racket-lang.org
Subject: Re: [racket] doubly linked list lib

[Laurent]

On Tue, Aug 30, 2011 at 12:23, Stephen Bloch <sbl...@adelphi.edu> wrote:

On Aug 30, 2011, at 3:18 AM, Laurent wrote:

Thank you very much for this nice intermediate solution, though I need constant-time append, split, insert, remove, + pointers to items, etc. Mutation does seem unavoidable, right.

The "zipper" structure Neil posted has constant-time append if you're already at the head of one zipper and the tail of the other, but in general it'll be linear time.  It has constant-time split, insert, and remove.

Not if you are not already at the right place in the lists.
Finding the place of the element in the list would take linear time.
 

 What do you mean by "pointers to items" -- that is, what do you need to DO with pointers to items?

Items are struct instances. By pointers I meant references, as they are handled automatically in Racket.
The list of items gives me a modifiable preference order on the items (the preference criterion may vary).
Each hash entry holds a "reference" to an item, and an item holds a reference to the previous and next elements in the list.
For example, given a key in the hash I get the reference to the item, and I can then put that element at the end of the list, or exchange it with the next element, or remove it, etc.
This does not seem possible with the same time complexity with zippers.

Laurent

[Laurent]

On Tue, Aug 30, 2011 at 12:52, Jos Koot <jos....@telefonica.net> wrote:

You are stating: hash with bounded memory

Does that mean you will have a limit on the number of entries?

Not necessarily. It might grow, although I might limit it to logarithmic growth.
Or the bound may be very large but unknown, and little memory should be used most of the time.
 

In that case a vector plus a current index might do, I think.

Gives you O(1) access to every element.

If the required number of elements may vary very much, a vector probably is not a good idea, unless using resizable vectors, but that makes some operations O(n).

A hash+vector would nearly do it, but in the end it might not get any simpler than a doubly linked list.
I also need to move items at the end of the list too.

I should add that this is not for production purpose, but for more "theoretical" properties, so I don't care much about a potential constant overhead per operation, but I care about how it would behave with an increasing number of items.

Laurent

[Hendrik Boom]

On Tue, Aug 30, 2011 at 02:29:34PM +0200, Laurent wrote:
> On Tue, Aug 30, 2011 at 12:52, Jos Koot <jos....@telefonica.net> wrote:
>

> > **

Would you lso want entries to be garbage-collected? If there are no
longer any references to a hash entry's key except as a key in the hash
table, would you want the garbage colelctor to be able to remove it?

-- hendrik

[Laurent]

Would you lso want entries to be garbage-collected?  If there are no
longer any references to a hash entry's key except as a key in the hash
table, would you want the garbage colelctor to be able to remove it?

You mean a weak hash? Possibly indeed, though I can remove them manually too. Would this change something?

Laurent

[Sam Tobin-Hochstadt]

I think there are some purely functional data structures that you can
use here. Two examples:

- Random Access Lists implemented in Hari Prashanth's Typed Purely
Functional Data Structures [1]
Some of the other data structures here, such as VLists, may also be helpful.

- David Van Horn's RAList package [2]

[1] http://planet.plt-scheme.org/package-source/krhari/pfds.plt/1/5/planet-docs/functional-data-structures/Random_Access_Lists.html
[2] http://planet.racket-lang.org/display.ss?package=ralist.plt&owner=dvanhorn

--
sam th
sa...@ccs.neu.edu

[Laurent]

Thank you very much, that looks good.

Laurent

[Marijn]

Hi Laurent,

On 08/30/11 09:18, Laurent wrote:
> Thank you very much for this nice intermediate solution, though I need
> constant-time append, split, insert, remove, + pointers to items, etc.
> Mutation does seem unavoidable, right.

I implemented a doubly-linked list, not so long ago, connected to a GUI
that can insert and delete items and saw no way to make the list
functional with multiple simultaneous editors in the GUI. The
implementation is as a straightforward cyclical doubly-linked list. I
toyed with the idea of having a separate handle object to represent the
list versus just the nodes, and there are some rudiments of that left in
the code, but in the end the user code uses a special 'top element to
indicate where the cyclical list is supposed to start.

Good luck,

Marijn

[Laurent]

Thank you Marjin, that looks nice.
Laurent

[Vincent St-Amour]

Are you planning to put this on PLaneT?

Vincent

At Wed, 31 Aug 2011 11:46:34 +0200,
Marijn wrote:
>
> [1 <multipart/signed (7bit)>]
> [1.1 <multipart/mixed (7bit)>]
> [1.1.1 <text/plain; ISO-8859-1 (quoted-printable)>]

> [1.1.2 dlist.rkt <text/plain (base64)>]
> (module dlist racket
> (provide dlist dl-insert dl-insert-right dl-remove for/dlist)
>
> (require (for-syntax racket))
>
> (define (dl-print dl p write?)
> (let ((print (if write? write display)))
> (display #\( p)
> (let loop ((l dl))
> (print (_dl-val l) p)
> (let ((right (_dl-right l)))
> (if (eq? right dl)
> (display #\) p)
> (begin (display " " p) (loop right)) )))))
>
> (define (dl-sequence l)
> (if (dl-empty? l)
> (make-do-sequence (lambda () (values #f #f #f (lambda (lk) #f) #f #f)))
> (let ((last (_dl-left l)))
> (make-do-sequence
> (lambda () ; val next start last?
> (values _dl-val _dl-right l #f #f (lambda (lk v) (not (eq? lk last)))) )))))
>
> ;;; link
> (define-struct _dl (left val right) #:mutable
> #:property prop:custom-write dl-print
> #:property prop:sequence dl-sequence
> ) ; end link
>
> (define (dlh-print dlh p write?)
> (dl-print (_dlh-link dlh) p write?))
>
> (define (dlh-sequence l)
> (let ((h (_dlh-link l)))
> (make-do-sequence
> (lambda () ; val next start last?
> (values _dl-val _dl-right (_dl-right h) (lambda (lk) (not (eq? lk h))) #f #f) ))))
>
> ;;; list handle
> (struct _dlh (link) #:mutable
> #:property prop:custom-write dlh-print
> #:property prop:sequence dlh-sequence
> ) ; end handle
>
> (define (dl-empty)
> (_dl #f #f #f))
>
> (define (dlh-empty)
> (_dlh (dl-empty)))
>
> (define (dl-empty? l)
> (not (_dl-left l)))
>
> (define (dl-one-element? l)
> (eq? l (_dl-left l)))
>
> (define (dlh-empty? l)
> (dl-empty? (_dlh-link l)))
>
> ; (define (dlist a b c)
> ; (shared ((la (_dl #f a lb))
> ; (lb (_dl la b lc))
> ; (lc (_dl lb c #f)) )
> ; la))
>
> (define-syntax (dlist stx)
> (syntax-case stx ()
> ((_) #'(dl-empty))
> ((_ a b ...)
> (let* ((temps (generate-temporaries #'(a b ...))) (links `(,(last temps) ,@temps ,(first temps))))
> #`(shared
> #,(let loop ((ret '()) (links links) (vals (syntax->list #'(a b ...))))
> (if (empty? vals) (reverse ret)
> (loop (cons #`(#,(cadr links) (make-_dl #,(car links) #,(car vals) #,(caddr links))) ret)
> (cdr links) (cdr vals) )))
> #,(cadr links))))))
>
> (define-syntax-rule (dlisth a b ...) (_dlh (dlist #f a b ...)))
>
> (define-syntax-rule (_dl-insert val link link-next new-link set-link-next! set-link-prev!)
> (if (dl-empty? link) (dlist val)
> (let* ((next (link-next link)) (new (new-link link val next)))
> (set-link-next! link new)
> (and next (set-link-prev! next new))
> new)))
>
> (define (dl-insert-right v l)
> (_dl-insert v l _dl-right _dl set-_dl-right! set-_dl-left!))
>
> (define (dl-insert v l)
> (let-syntax ((dl (syntax-rules () ((_ r v l) (_dl l v r)))))
> (_dl-insert v l _dl-left dl set-_dl-left! set-_dl-right!)))
>
> (define-syntax-rule (_dlh-insert v l insert)
> (let ((h (_dlh-link l)))
> (if h
> (insert v h)
> (set-_dlh-link! l (dlist v)) )))
>
> (define (dlh-insert-front v l)
> (_dlh-insert v l dl-insert-right))
>
> (define (dlh-insert-back v l)
> (_dlh-insert v l dl-insert))
>
> (define (dl-remove link (ret #f))
> (if (or (dl-empty? link) (dl-one-element? link))
> (dl-empty)
> (let ((l (_dl-left link)) (r (_dl-right link)))
> (set-_dl-right! l r)
> (set-_dl-left! r l)
> (if ret l r))))
>
> (define (dl-reverse link)
> (if (dl-empty? link) (dl-empty)
> (let ((left (_dl-left link)) (right (_dl-right link)))
> (set-_dl-right! link left)
> (set-_dl-left! link right)
> (let loop ((lft link) (lnk right))
> (if (eq? lnk link) left
> (let ((rght (_dl-right lnk)))
> (set-_dl-right! lnk lft)
> (set-_dl-left! lnk rght)
> (loop lnk rght)))))))
>
> ; (define (dlh-reverse l)
>
> (define-syntax-rule (for/dlist clauses body ... val)
> (_dl-right (for/fold ((ret (dl-empty))) clauses (dl-insert-right val ret))))
>
> ) ; end module
> [1.1.3 list-editor.rkt <text/plain; UTF-8 (quoted-printable)>]
> #lang racket/gui
>
> ;(require dlist)
> (require "./dlist.rkt")
>
> (define list-editor%
> (class vertical-panel%
> (init init-values parent)
> (super-new (parent parent))
>
> (define widget-list (dlist 'top))
>
> (define (redisplay)
> (send this change-children (lambda (l) (cdr (for/list ((w widget-list)) w)))))
>
> (define (insert-item val link)
> (let* ((v (new vertical-panel% (parent this)))
> (lk (dl-insert v link))
> (ins (new button% (parent v) (label "insert")
> (callback (λ (b e)
> (insert-item "1" lk) (redisplay) )) ) )
> (h (new horizontal-pane% (parent v)))
> (t (new text-field% (parent h) (label "") (init-value val)))
> (del (new button% (parent h) (label "del")
> (callback (λ (b e) (dl-remove lk) (send this delete-child v))) )))
> lk))
>
> ; (send this begin-container-sequence)
> (for ((v init-values)) (insert-item v widget-list))
> ; (send this end-container-sequence)
>
> (let* ((v (new vertical-panel% (parent this)))
> (lk (dl-insert v widget-list)))
> (new button% (parent v) (label "append")
> (callback (λ (b e) (insert-item "1" lk) (redisplay))) ))
>
> )) ; end define class
>
> (define root (new frame% (label "List Editor") (stretchable-height #f)))
>
> (new list-editor% (parent root) (init-values '("1" "2" "3")))
>
> (send root show #t)
> [1.2 OpenPGP digital signature <application/pgp-signature (7bit)>]
>
> [2 <text/plain; us-ascii (7bit)>]

[Marijn]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Hi Vincent,

On 08/31/11 17:50, Vincent St-Amour wrote:
> Are you planning to put this on PLaneT?
>
> Vincent

I wasn't. This code has seen very little testing and has so far only
been used in toy/throw-away code. The Gambit community has a
no-expectation-of-quality place to dump code, appropriately called the
Dumping Grounds[1]. If this was the gambit mailing list I would have
said "sure I'll dump it", but I don't think I am ready to inflict it
on Planet. Maybe my expectations of code on Planet is off, or maybe
racket also needs a Dumping Grounds...

Marijn

[1]:http://dynamo.iro.umontreal.ca/~gambit/wiki/index.php/Dumping_Grounds

> At Wed, 31 Aug 2011 11:46:34 +0200, Marijn wrote:
>>
>> [1 <multipart/signed (7bit)>] [1.1 <multipart/mixed (7bit)>]
>> [1.1.1 <text/plain; ISO-8859-1 (quoted-printable)>] Hi Laurent,
>>
>> On 08/30/11 09:18, Laurent wrote:
>>> Thank you very much for this nice intermediate solution, though
>>> I need constant-time append, split, insert, remove, + pointers
>>> to items, etc. Mutation does seem unavoidable, right.
>>
>> I implemented a doubly-linked list, not so long ago, connected to
>> a GUI that can insert and delete items and saw no way to make the
>> list functional with multiple simultaneous editors in the GUI.
>> The implementation is as a straightforward cyclical doubly-linked
>> list. I toyed with the idea of having a separate handle object to
>> represent the list versus just the nodes, and there are some
>> rudiments of that left in the code, but in the end the user code
>> uses a special 'top element to indicate where the cyclical list
>> is supposed to start.
>>
>> Good luck,
>>
>> Marijn

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.18 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iEYEARECAAYFAk5grQsACgkQp/VmCx0OL2yB7ACfVmnT7S7y0pvTvUa7mtkRg8EN
GRwAn0DHnPxrnT/+we0gIuvufQRMv3SF
=fD70
-----END PGP SIGNATURE-----

[Laurent]

On Fri, Sep 2, 2011 at 12:16, Marijn <hk...@gentoo.org> wrote:

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Hi Vincent,

On 08/31/11 17:50, Vincent St-Amour wrote:
> Are you planning to put this on PLaneT?
>
> Vincent

I wasn't. This code has seen very little testing and has so far only
been used in toy/throw-away code. The Gambit community has a
no-expectation-of-quality place to dump code, appropriately called the
Dumping Grounds[1]. If this was the gambit mailing list I would have
said "sure I'll dump it", but I don't think I am ready to inflict it
on Planet. Maybe my expectations of code on Planet is off, or maybe
racket also needs a Dumping Grounds...

I think this is what Jukka is has in mind:
http://www.mail-archive.com/us...@racket-lang.org/msg07569.html

Laurent
 

[Jukka Tuominen]

Exactly. The fastest way is to

 

1) Add a link to the 'announcements' section like this [[name]]    (before adding the actual article)

2) click on the newly created link, and paste your code there with <pre>   code here   </pre>  tags

 

br, jukka

 

-----Original Message-----
From: Laurent [mailto:laurent...@gmail.com]
Sent: 02 September 2011 13:25
To: Marijn; Jukka Tuominen
Cc: Vincent St-Amour; us...@racket-lang.org
Subject: Re: [racket] doubly linked list lib