CODEWITHSUNDEEP
listprologtranslationrepresentation
John Smith
John Smith

Reputation: 181

Prolog: List translation

I've been trying to figure out what list another list representation corresponds to:

[1|[2|[3|[4|[]]]]] is equivalent to the list [1,2,3,4] and [1,2,3,4|[]] etc.

But I just can't seem to figure out what list this corresponds to:

[[[[[]|1]|2]|3]|4]

If anyone can explain this for me I would be very grateful.

Upvotes: 1

Views: 282

Answers (2)

lurker
lurker

Reputation: 58254

[H|T] is syntactic sugar for the real representation using the . functor: .(H,T) where H is the "head" (one list element), and T is the "tail" (which is itself a list in a standard list structure). So [1|[2|[3|[4|[]]]]] is .(1,.(2,.(3,.(4,[])))). Prolog also allows a non-list value for T, so [[[[[]|1]|2]|3]|4] is .(.(.(.([],1),2),3),4). The second structure doesn't really simplify any further than that from a list notational standpoint.

If you want to think in terms of "list" then [[[[[]|1]|2]|3]|4] is a list whose head is [[[[]|1]|2]|3] and tail is 4. And since 4 is not a list, the original list can be described as "improper" as @z5h indicated since the tail isn't a list (not even the empty list). Drilling down, the head [[[[]|1]|2]|3] is itself a list with head [[[]|1]|2] and tail 3. Another "improper" list. And so on. Therefore, the overall structure is an embedded list of lists, four levels deep, in which each list has a single head and a non-list tail (an "improper" list).

It's interesting to note that some of Prolog's predicates handle this type of list. For example:

append([], 1, L).

Will yield:

L = [[]|1]

You can then build your oddly formed list using append:

append([[]], 1, L1),   % append 1 as the tail to [[]] giving L1
append([L1], 2, L2),   % append 2 as the tail to [L1] giving L2
append([L2], 3, L3),   % append 3 as the tail to [L2] giving L3
append([L3], 4, L4).   % append 4 as the tail to [L3] giving L4

Which yields:

L4 = [[[[[]|1]|2]|3]|4]

Each append takes a list of one element (which is itself a list from the prior append, starting with [[]]) and appends a non-list tail to it.

Upvotes: 2

Mark Bolusmjak
Mark Bolusmjak

Reputation: 24409

It's called an "improper list".

Let me explain.

I think a few different ideas are at play here.
In general we know what a list is: it's an ordered collection.

How we represent a list literal in a programming language is another facet.
How the list is represented internally in the language, is another facet still.

What you have realized, is that there is a data structure you can represent in Prolog, with similar syntax to a list, but it somehow seems "improper". (It's not clear that you have asked much beyond "what is the meaning of this confusing thing?").

It turns out, that this structure is simply known as an "improper list". This data structure shows up often in languages that store lists internally as nested cons cells or similar. If you Google for that, you'll find plenty of resources for examples, usages, etc.

Upvotes: 1

Related Questions