Haskell (:) và (++) sự khác biệt

Question

Tôi xin lỗi vì một câu hỏi như thế này. Tôi không quá chắc chắn về sự khác biệt của các nhà điều hành : và ++ trong Haskell.

x:y:[] = [x,y] 

cũng

[x] ++ [y] = [x,y] 

như đối với các chức năng ngược lại mà nảy sinh câu hỏi này đối với tôi,

reverse ::[a]->[a] 
reverse [] = [] 
reverse (x:xs) = reverse(xs)++[x] 

Tại sao không phải là công việc sau đây?

reversex ::[Int]->[Int] 
reversex [] = [] 
reversex (x:xs) = reversex(xs):x:[] 

đưa ra lỗi loại.

Answer 1

Nhà điều hành : được gọi là "khuyết điểm" nhà điều hành và được sử dụng để thêm vào trước một yếu tố đầu vào một danh sách. Vì vậy, [] là một danh sách và x:[] đang chờ thêm x vào danh sách trống để tạo danh sách [x]. Nếu sau đó bạn vi phạm y:[x], bạn sẽ có danh sách [y, x] tương tự như y:x:[].

Toán tử ++ là toán tử ghép nối danh sách có hai danh sách làm toán hạng và "kết hợp" chúng thành một danh sách duy nhất. Vì vậy, nếu bạn có danh sách [x] và danh sách [y] thì bạn có thể nối chúng như sau: [x]++[y] để nhận [x, y].

Lưu ý rằng : lấy một phần tử và danh sách trong khi ++ có hai danh sách.

Đối với mã của bạn không hoạt động.

reversex ::[Int]->[Int] 
reversex [] = [] 
reversex (x:xs) = reversex(xs):x:[] 

Hàm đảo ngược đánh giá vào danh sách. Vì toán tử : không lấy danh sách làm đối số đầu tiên nên reverse(xs):x không hợp lệ. Nhưng reverse(xs)++[x] là hợp lệ.

Answer 2

: giao một phần tử vào danh sách.

++ nối thêm hai danh sách.

Các cựu có kiểu

a -> [a] -> [a] 

trong khi sau này có kiểu

[a] -> [a] -> [a] 

Answer 3

Concatenation với (++)

Có lẽ tôi đang nghĩ đến sâu vào điều này, nhưng, như xa như tôi hiểu, nếu bạn cố gắng nối danh sách sử dụng (++) ví dụ:

[1, 2, 3] ++ [4, 5] 

(++) phải duyệt qua danh sách bên trái hoàn chỉnh. Hãy xem số code of (++) làm cho nó tất cả rõ ràng hơn.

(++) :: [a] -> [a] -> [a] 
(++) []  ys = ys 
(++) (x:xs) ys = x : xs ++ ys 

Do đó, nó sẽ được mong muốn để tránh sử dụng (++), vì với mỗi cuộc gọi reverse(xs)++[x] danh sách ngày càng lớn hơn (hoặc nhỏ hơn tùy thuộc trên quan điểm. Dù sao, chương trình chỉ đơn giản là phải đi qua khác danh sách với mỗi cuộc gọi)

Ví dụ:

phép nói rằng tôi thực hiện ngược lại theo đề nghị thông qua nối.

reversex ::[Int]->[Int] 
reversex [] = [] 
reversex (x:xs) = reversex(xs)++[x] 

Đảo ngược một danh sách [1, 2, 3, 4] sẽ trông hơi như thế này:

reversex [1, 2, 3, 4] 
reversex [2, 3, 4]    ++ [1] 
reversex [3, 4]   ++ [2] ++ [1] 
reversex [4]  ++ [3] ++ [2] ++ [1] 
reversex [] ++ [4] ++ [3] ++ [2] ++ [1] 
     [] ++ [4] ++ [3] ++ [2] ++ [1] 
     [4]  ++ [3] ++ [2] ++ [1] 
     [4, 3]   ++ [2] ++ [1] 
     [4, 3, 2]    ++ [1] 
     [4, 3, 2, 1] 

Tail Recursion sử dụng toán tử khuyết điểm (:) !!!

Một phương pháp để xử lý ngăn xếp cuộc gọi là thêm accumulator. (nó không phải luôn luôn có thể chỉ cần thêm một ắc. Nhưng hầu hết các chức năng đệ quy một giao dịch với rất primitive recursive và do đó có thể được chuyển đổi thành tail recursive functions.)

Với sự giúp đỡ của accumulator nó có thể làm cho ví dụ này hoạt động, sử dụng toán tử cons (:). Bộ tích lũy - ys trong ví dụ của tôi - tích lũy kết quả hiện tại và được truyền đi như một tham số. Do bộ tích lũy, chúng tôi hiện có thể để sử dụng toán tử cons để tích lũy kết quả bằng cách nối thêm đầu danh sách ban đầu của chúng tôi mỗi lần.

reverse' :: (Ord a) => [a] -> [a] -> [a] 
reverse' (x:xs) ys = reverse' xs (x:ys) 
reverse' [] ys  = ys 

Có một điều cần lưu ý ở đây.

Bộ tích lũy là một đối số bổ sung. Tôi không biết nếu Haskell cung cấp các thông số mặc định, nhưng trong trường hợp này nó sẽ được tốt đẹp, bởi vì bạn sẽ luôn luôn gọi hàm này với danh sách trống như accumulator như vậy: reverse' [1, 2, 3, 4] []

Có rất nhiều văn học về việc đệ quy đuôi và tôi là chắc chắn có rất nhiều câu hỏi tương tự trên StackExchange/StackOverflow. Hãy sửa tôi nếu bạn tìm thấy bất kỳ sai lầm nào.

Trân trọng!

EDIT 1:

Will Ness chỉ ra một số liên kết câu trả lời cho thực sự tốt đối với những người bạn của những người quan tâm:

• Why are difference lists more efficient than regular concatenation?
• Haskell foldl' poor performance with (++)

EDIT 2:

Ok. Nhờ dFeuer và chỉnh sửa của mình Tôi nghĩ rằng tôi hiểu Haskell tốt hơn một chút.

1.The $! nằm ngoài hiểu biết của tôi. Trong tất cả các thử nghiệm của tôi, dường như khiến mọi việc trở nên tồi tệ hơn.

2.As dFeuer chỉ ra: Các thunk đại diện cho các ứng dụng của (:) để x và y là ngữ nghĩa giống với x:y nhưng phải mất nhiều bộ nhớ hơn. Vì vậy, điều này là đặc biệt đối với nhà điều hành cons (và các nhà xây dựng lười biếng) và không cần phải ép buộc mọi thứ theo bất kỳ cách nào.

3. Nếu tôi thay sumUp Số nguyên của một danh sách sử dụng một chức năng rất giống nhau, đánh giá nghiêm ngặt thông qua BangPatterns hoặc seq chức năng sẽ ngăn chặn ngăn xếp từ phát triển quá lớn nếu được sử dụng một cách thích hợp. ví dụ:

sumUp' :: (Num a, Ord a) => [a] -> a -> a 
sumUp' (x:xs) !y = reverse' xs (x + y) 
sumUp' [] y  = y 

Lưu ý trường ở phía trước của y. Tôi đã thử nó trong ghci và nó mất ít bộ nhớ hơn.

Answer 4

cons có xu hướng trở thành nhà xây dựng kiểu so với toán tử. ví dụ ở đây là : có thể được sử dụng trong let..in.. expresion nhưng ++ không

let x : xs = [1, 2, 3] in x -- known as type deconstructing 

sẽ trở lại 1 nhưng

let [x] ++ [y, z] = [1, 2, 3] in x 

sẽ trả về một lỗi Variable not in scope x

Để làm cho nó dễ dàng, nghĩ về cons như thế này

data List a = Cons a (List a) -- is equvalent with `data [a] = a:[a]` 

https://en.wikibooks.org/wiki/Haskell/Other_data_structures

Ngoài ra, nếu bạn muốn đảo ngược mảng bằng khuyết điểm. Dưới đây là một ví dụ, kiến ​​thức được lấy từ Prolog

import Data.Function 

reversex1 [] = [] 
reversex1 arr = reversex arr [] 

reversex [] arr = arr 
reversex (x:xs) ys = reversex xs (x:ys) 

main = do 
    reversex1 [1..10] & print