What is a proper list?

Questions / Help
1

Hi all
Can please someone explain me what a properlist is?

THanks

1 Like
2

A Proper List is a list with the last-most tail being an empty list.

Think of it this way, a list is just a set of Cons cells, which you can think of just as 2-tuple like {head, tail}, though we write it as [head | tail]. The empty list [] is basically just a point to a permanent ‘list’ chunk that is always empty. Setting the tail to the empty list, like [head | []] is a Proper list, regardless of what head contains (which could be items, or another list entirely).

Why this is a proper list is because it makes iteration over lists a little bit easier, as to test that you are at the end you just compare the list to being [] or not. The system could have easily used about anything to signify an empty list, but a unique type means that we can put anything in the tail if we really want without worry that it means something else if someone needs an improper list for some reason.

3 Likes
3

I don’t think that’s quite right. I would describe it as a list where all tails point to another list.

1 Like
4

Not entirely…

Technically [] is not a list, it is an empty list, it has a different storage id in the engine, specifically it is ID 106, a normal list has ID 108 and a char list has ID 107. :slight_smile:

Side Note: Interestingly, ID 106 is internally to erlang called the nil, yet Elixir’s nil does not map to it. Elixir’s nil is just an atom, no more special than that.

EDIT: I’ve made… too many libraries than I’d care to admit parsing the erlang term format… I know it quite well. >.>

5 Likes
5

I stand corrected. Thanks.

5 Likes
6

Erlang Term Format does not map 100% to how things work on the VM - it’s optimised for ease of transfer and parsing. There are two different formats for charlists and regular lists in the ETF, yet they are represented exactly the same at runtime and have the same semantics.

I think we’re confusing semantics of the language with the implementation. An empty list is a list as well - this can be checked with is_list([]), which returns true. The fact that it’s represented differently in memory, is not important, unless you’re playing with ERTS itself and the BEAM implementation.

2 Likes
7

From my experiences it is how it works on the VM, however it is not how things work in the HiPe JIT (which, unfortunately my platform does not support), but all interfacing with the VM is via the erlang term format. :slight_smile:

Just because we have a higher level language on top does not change how it works underneath, and the VM does define a proper list as a list with a Cons Cell Tail of one of those three list types, only. :slight_smile:

1 Like
8

I prefer the ADT style definition of a list as
‘’’
@type list :: [] | [ term | list ]
‘’’

I feel like it captures the nature of linked lists nicely

1 Like
9

Ditto yeah, I really really badly want Elixir to be typed at compile-time, could enforce such proper-lists then when necessary instead of getting surprised at random run-time errors. :slight_smile:

2 Likes
10

Dialyzer is unfortunately the best we have at the moment.

2 Likes
11

So it is save to say proper list = list?

12 
iex(1)> properList = [1 | [2 | [3 | []]]] # note the "[]" 
[1, 2, 3]
iex(2)> improperList = [1 | [2 | 3]]      # note NO "[]"
[1, 2 | 3]
iex(3)> is_list(properList)
true
iex(4)> is_list(improperList)
true
iex(5)> Enum.map properList, &(&1)
[1, 2, 3]
iex(6)> Enum.map improperList, &(&1)
** (FunctionClauseError) no function clause matching in Enum."-map/2-lists^map/1-0-"/2
    (elixir) lib/enum.ex:1184: Enum."-map/2-lists^map/1-0-"(#Function<6.52032458/1 in :erl_eval.expr/5>, 3)
    (elixir) lib/enum.ex:1184: Enum."-map/2-lists^map/1-0-"/2
    (elixir) lib/enum.ex:1184: Enum."-map/2-lists^map/1-0-"/2
2 Likes
13

The difference between properlist and improperlist is the end []. Why you can not pass a improperlist to enum map?

14

A usual implementation for map does match on [] as its end-condition. Also it is not always clear for an improper list, if that last tail has a special meaning or if it should be considered data.

15

What are the use case(s) for improper lists?

1 Like
16

The “io_list” is a very good example, it allows O(1) “append”. ["Hello, "|"andre1sk"]

1 Like
17

Lazy List (generators).

1 Like
18

http://www.erlangpatterns.org/iolist.html

1 Like
19

Be careful not to create an improper list.

Suggesting that [quote=“NobbZ, post:16, topic:1400”]
["Hello, "|"andre1sk"]
[/quote]

should be ["Hello, " | ["andre1sk"]]

20

Yeah, that’s weird. That second list serves no purpose.