What are the benefits of Cons?

Many functional programming languages ​​support and recommend the Cons data constructor (for lists such as (1, (2, (3))) such as Haskell and Scala .

But what are its advantages? Such lists cannot be randomly accessed or added to O(1) .

+4
source share
2 answers

Cons (short for construct) is not a data structure; it is the name of the operation to create a cons-cell. And by combining several cells, you can build a data structure, in particular - a linked list. The rest of the discussion assumes that the linked list is created using Cons operations.

Although it is possible to add to O (1) in the chapter, random access to elements by index is an expensive operation that requires traversing all the elements to the one accessed.

Benefits of a linked list? it is a functional data structure, cheap to create or recreate in case of modifications; it allows nodes to be exchanged between multiple lists and makes it easy to collect garbage. It is very flexible, with the right abstractions, it can represent other, more complex data structures, such as stacks, queues, trees, graphs. And there are many, many procedures written specifically for manipulating lists - for example, map , filter , fold , etc., which make working with lists a joy. Finally, a list is a recursive data structure, and recursion (especially tail recursion) is the preferred way to solve problems in functional programming languages; therefore, in these languages ​​it is natural to have a recursive data structure as the main data structure.

+6
source

First of all, let it distinguish “cons” as a nickname for the ML-style list data constructor, usually called :: , and where the nickname starts from, the original Lisp-style cons function.

In Lisps, cons cells are a universal data structure that is not limited to lists of a homogeneous element type. The equivalent in ML style languages ​​must be nested pairs or two tuples, and an empty list represented by a “single” type is often written () . Óscar López gives a good overview of the utility of Lisp cons , so I will leave it to that.

In most ML style languages, the benefits of indispensable flaw lists are not too different from using them for Lisps lists, which eliminates the flexibility of dynamic input to guarantee static input and the syntax for matching the ML style template.

At Haskell, however, the situation is quite different due to a lazy assessment. Constructors are lazy, and matching patterns on them is one of the few ways to force evaluation, so, unlike strictly evaluated languages, it often happens that you should avoid tail recursion. Instead, by placing a recursive call at the tail of the list, it becomes possible to compute each recursive call only when necessary. If a lazily-generated list is processed using correspondingly lazy functions, such as map or foldr , it becomes possible to build and use a large list in read-only memory, while the tails will be forced to throw heads at the same speed for the GC to clear.

The general perspective in Haskell is that a list of lazy minuses is not so much a data structure as a management structure - a reified loop that effectively links with other such loops.

However, there are many cases where the list of flaws is not suitable - for example, when repeated random access is required - and in those situations where the lists are certainly not recommended.

+2
source

All Articles