2009-02-13

Lisp, Ocaml, Linked List

2009-02-13

Dear Jon idiot,

No, Ocaml doesn't have linked list. Looook:

> [1;2;3]

That's a sequence of 3 numbers, separated by semicolon, then bracketed by square brackets. As flat as you can see.

> h::t

That's ocaml's syntax to deconstruct a sequece of things by pattern
matching the first element and the rest elements, so that programers
can retrieve either the first element or rest elements.

> 1 :: [2;3]

That's a syntax for prepending the element 1 to the flat sequece of 2 and 3. No link in sight.

> From Jon idiot's point of view, Mathematica...

O, Mathematica has linked list. Look:

{1,{2,{3,{}}}}
A B C

The list A's second element is referenced to the list B, who's second element is linked to list C. See? Linked!

O, i forgot, that you forgot to define what you mean by linked list. You wrote:

> Not abstract. A linked list is a concrete data structure composed of cells
> that refer to each other by reference (the links) in a linear sequence.
> Singly-linked lists have references only in one direction. Double-linked
> lists have references in both directions. Immutable lists forbit the
> references to be mutated but the elements of the list may still be mutable.

ummm.... egadz, so do you mean linked list is a computer language engineering issue?? How's this apply to your example of Ocaml and opinion of Mathematica? Do you mean their compilers work in certain way therefore Ocaml has links and Mathematica don't? What is the relation of how the compiler works to users of the lang? Does the language C has linked list by your definition?

What lang has linked list by your definition above? Does Perl, Python, PHP, Java? I tried to think this, but your def is impricise. What's a “cell”, “linear sequence”? I mean, it has lots meanings in math, computer science... depending what special context you are talking about. The term “data structure” itself is quite flexible too. I mean, don't you agree that you can implement any data structure with turing machines too? In your fuzzy definition, then the Mathematica “{1,{2,{3,{}}}}” is a linked list right? From your def: “data structure”, check. “composed of cells”, check, “refers to each by reference in a linear sequence”, check.

Xah
∑ http://xahlee.org/



http://groups.google.com/group/comp.lang.lisp/browse_frm/thread/326b50adea373c23

No comments:

Post a Comment