Why do functional languages ​​use lists so much?

Question

I mean, what are the advantages of a list in other data structures that make it almost inevitable in functional languages?

Answer 1

"No spoon."

What if I told you that there are no strings like strings? There is only a list of single characters.

Then what if I told you that there is no such thing as a list? There are only couples.

; construct a pair of a and b
(cons 'a 'b)           ; => ('a 'b)

; get the first element of the pair
(first (cons 'a 'b))   ; => 'a

; get the second element of the pair
(second (cons 'a 'b))  ; => 'b

; create a "list"
(define x (cons 'a (cons 'b (cons 'c (cons 'd (cons 'e null))))))
; => ('a ('b ('c ('d ('e ())))))

; get the third element in the "list", x
(first (second (second x)))
; => 'c

Now, what if I told you that such pairs do not exist? There is only lambda.

(define (cons x y)
  (λ (f) (f x y)))

(define (first p)
  (p (λ (x y) x)))

(define (second p)
  (p (λ (x y) y)))

Of course, this is just one possible implementation. But it is important to understand that all this is just an illusion.

. , , /, . , .

, , , . . , , - ^, ^

Answer 2

, , , . , , , . , .

. , -F #:

let array1 = [| 1, 2, 3, 4, 5 |]
let array2 = append 6 array1 // [| 1, 2, 3, 4, 5, 6 |]

append, n+1 array1 .

, , append n , .

:

type List<'a> = 
    |Empty
    |Cons of 'a * List<'a>

Cons, .

1 :

let list1 = [1..1000000]
let list2 = Cons (0, list1) // [0..1000000]

list2 list1, . , - O (1), , .

, . , Deques Priority.

, , , , .