lập trình viên haskell mới bắt đầu

Question

isPalindrome::(Eq a) => [a] -> Bool 
isPalindrome [] = True 
isPalindrome [x] = True 
isPalindrome (x1:xs:x2:[]) 
    | x1 == x2 = isPalindrome xs 
    |otherwise = False 


[1 of 1] Compiling Main    (myHas.hs, interpreted) 

myHas.hs:37:27: 
    Couldn't match expected type `[a]' against inferred type `a1' 
     `a1' is a rigid type variable bound by 
      the type signature for `isPalindrome' at myHas.hs:33:18 
    In the first argument of `isPalindrome', namely `xs' 
    In the expression: isPalindrome xs 
    In the definition of `isPalindrome': 
     isPalindrome (x1 : xs : x2 : []) 
         | x1 == x2 = isPalindrome xs 
         | otherwise = False 

Tôi là người lập trình haskell mới bắt đầu và không có đầu mối về lý do tại sao tôi nhận được lỗi này, bất kỳ trợ giúp nào?

Answer 1

Bạn đối xử với xs giống như danh sách, nhưng (x1:xs:x2:[]) giả định đó là một phần tử trong danh sách đầu vào của bạn.

Lưu ý rằng (x1:xs:x2:[]) sẽ phù hợp chỉ liệt kê với 3 yếu tố, và x1, xs và x2 sẽ phần tử kiểu a.

Vì vậy xs là loại a, nhưng khi bạn vượt qua nó để isPalindrome, chúng tôi chỉ có thể giả định nó phải là một danh sách một cái gì đó, vì vậy hệ thống kiểu gọi loại [a1].

Cách đơn giản nhất để mã hóa những gì bạn muốn là:

isPalindrome::(Eq a) => [a] -> Bool 
isPalindrome l = l == (reverse l) 

Answer 2

Đây là một cách dễ dàng để hiểu câu trả lời, tương tự như nỗ lực của bạn:

isPalindrome [] = True 
isPalindrome [x] = True 
isPalindrome xs = (head xs == last xs) && isPalindrome (init (tail xs)) 

Vì vậy, một danh sách rỗng hoặc một phần tử là palindrome và danh sách dài hơn là palindrome nếu phần tử đầu tiên và cuối cùng bằng nhau và các phần tử "ở giữa" cũng là palindrome.

Lưu ý rằng câu trả lời của MGwynne là nhiều hơn hiệu suất cao hơn, vì giải pháp trên phải duyệt qua danh sách trong mỗi bước.

Answer 3

Tôi cảm thấy rằng một giải thích về cú pháp được sử dụng cho danh sách là cần thiết ở đây, mà chưa được đưa ra cho đến nay. trước hết, định nghĩa của các loại danh sách trong Haskell là:

data [a] = a : [a] | [] 

nào nói rằng một danh sách là một trong hai rỗng ([]) hoặc nó được làm từ (:) constructor, trong đó có như là đối số bên trái của nó một a, và một danh sách khác (số [a] trong định nghĩa). Điều này có nghĩa là danh sách [1,2,3] thực sự là 1 : (2 : (3 : [])), nhưng điều này cũng có thể được viết là chỉ 1 : 2 : 3 : [].

Khi mô hình kết hợp vào một danh sách, bạn phù hợp với các nhà xây dựng:

f [] = … -- match the empty list 

f (x:[]) = … -- match a list with one element, which you name x 

f (x:xs) = … -- match the first element of the list, and whatever the rest of 
      -- the list is, but it must have at least one element. if you call 
      -- f [1,2,3], x will be bound to 1, and xs will be bound to [2,3] 
      -- because [1,2,3] is the same as (1:[2,3]) 

f (x:y:xs) = … -- matches a list with at least two elements, which you 
       -- call x and y respectively 

f (xs:ys:zs:things) = … -- matches a list with at least three elements, 
         -- which you name, xs, ys and zs. 

Vì vậy, từ này, hy vọng nó bây giờ rõ ràng rằng

f (x1:xs:x2:[]) 

phù hợp với một danh sách với chính xác ba yếu tố, mà bạn đặt tên x1, xs và x2.

Tôi hy vọng điều đó sẽ hữu ích.