Show HN: New Lisp data structure

Re:Show HN: New Lisp data structure by rntz on Wednesday December 01, 2010 @06:50PM (#1960280)

The two most common operations on lists in typical functional programs are consing and deconsing, which are O(1). The most analogous operations on trellises are appending and removing the tail element, which are O(log n). So it seems inappropriate to propose trellises as general replacements for lists.

Indeed, I'm not sure in what situations this tradeoff of cons/decons- for lookup-speed is helpful. If I just need fast lookup, I'll use a mapping structure (hashtable, balanced binary tree, patricia trie, etc). If I need reasonable lookup speed and also standard sequence manipulations, finger trees or ropes seem like a better choice. They're more complex, but if performance is an issue, then it's probably worth it.

Also, a bug/design flaw: You can't store NILs in the terminal position:

   > (trellis 1 2)
   (1 (2))
   > (trellis 1 2 nil)
   (1 (2))

[ Parent | on HN ]

Re:Show HN: New Lisp data structure by daniel-cussen on Wednesday December 01, 2010 @06:55PM (#1960304)

About the bug, I talk about this at the end of trellis2.lisp. I didn't want to weird people out by adding a second sentinel to the list.

I realize these aren't the best at any one thing, but in situations where you'd normally use lists (exploratory programming, say) you can swap to this for a performance boost.

[ Parent | on HN ]

Re:Show HN: New Lisp data structure by jules on Wednesday December 01, 2010 @07:40PM (#1960447)

That's just broken, and will lead to horrible bugs. There is a reason why normal Lisp lists end with NIL instead of storing the last element in the last cdr.

[ Parent | on HN ]

Re:Show HN: New Lisp data structure by daniel-cussen on Wednesday December 01, 2010 @08:00PM (#1960504)

> That's just broken, and will lead to horrible bugs.

You mean you think people will use this? Thanks :)

Here's how I was thinking of fixing it:

(setf nol 'nol) ; make nol evaluate to itself

(defun my-null (x) ;redefine null (if (or (null x) (eql nol x)) t null))

Then, change add so that if it's adding a nil, it changes the sentinel at the end of the linked list part of the list to nol.

So (trellis 1 2) returns (1 . ((2 . NIL) . NIL))

And (add nil (trellis 1 2)) returns (1 . ((2 . NIL) . NOL))

As soon as someone adds something other than a nil to a cdr of a cons in a tree, add changes nol back to nil.

[ Parent | on HN ]

Re:Show HN: New Lisp data structure by alec on Wednesday December 01, 2010 @08:28PM (#1960583)

Use gensym to make a unique sentinel.

[ Parent | on HN ]

Re:Show HN: New Lisp data structure by Shamiq on Thursday December 02, 2010 @01:45AM (#1961314)

To clarify, you mean: (setf nol (gensym)) instead of (setf nol 'nol)?

[ Parent | on HN ]