Ứng dụng chức năng Haskell và currying

Question

Tôi luôn quan tâm đến việc học các ngôn ngữ mới, một thực tế giữ tôi trên các ngón chân và làm cho tôi (tôi tin) là một lập trình viên tốt hơn. Nỗ lực của tôi trong việc chinh phục Haskell đến và đi - hai lần cho đến nay - và tôi quyết định đã đến lúc thử lại. Lần thứ ba là sự quyến rũ, phải không?

Không. Tôi đã đọc lại những ghi chép cũ của mình ... và cảm thấy thất vọng :-(

Vấn đề khiến tôi mất niềm tin lần trước, là một vấn đề dễ dàng: hoán vị số nguyên. tức là từ danh sách số nguyên danh sách - một danh sách các hoán vị của họ:

[int] -> [[int]] 

này là trong thực tế là một vấn đề chung chung, do thay thế 'int' trên với 'a', vẫn sẽ áp dụng

Từ ghi chú của tôi:

.

Tôi tự viết mã lần đầu tiên, tôi thành công. Hoan hô!

Tôi gửi giải pháp cho một người bạn tốt của tôi - Haskell guru, nó thường giúp học hỏi từ rất kinh nghiệm - và anh ấy gửi cho tôi điều này, mà tôi được nói, "thể hiện sức mạnh thực sự của ngôn ngữ, sử dụng chung cơ sở để mã hóa nhu cầu của bạn ". Tất cả cho nó, gần đây tôi đã uống kool-aid, chúng ta hãy đi:

permute :: [a] -> [[a]] 
permute = foldr (concatMap.ins) [[]] 
    where ins x []  = [[x]] 
     ins x (y:ys) = (x:y:ys):[ y:res | res <- ins x ys] 

Hmm. Hãy chia nhỏ phần này:

bash$ cat b.hs 
ins x []  = [[x]] 
ins x (y:ys) = (x:y:ys):[ y:res | res <- ins x ys] 

bash$ ghci 
Prelude> :load b.hs 
[1 of 1] Compiling Main    (b.hs, interpreted) 
Ok, modules loaded: Main. 

*Main> ins 1 [2,3] 
[[1,2,3],[2,1,3],[2,3,1]] 

OK, cho đến nay, rất tốt. Đã cho tôi một phút để hiểu dòng thứ hai của "ins", nhưng OK: Nó đặt các arg 1 trong tất cả các vị trí có thể có trong danh sách. Mát mẻ.

Bây giờ, để hiểu foldr và concatMap. trong "Real thế giới Haskell", DOT được giải thích ...

(f . g) x 

... như chỉ là một cú pháp cho ...

f (g x) 

Và trong mã guru gửi, DOT đã được sử dụng từ một foldr, với "in" chức năng như nếp gấp "sụp đổ":

*Main> let g=concatMap . ins 
*Main> g 1 [[2,3]] 
[[1,2,3],[2,1,3],[2,3,1]] 

OK, vì tôi muốn hiểu như thế nào DOT được sử dụng bởi guru, tôi cố gắng biểu hiện tương đương theo định nghĩa DOT , (f. g) x = f (gx) ...

*Main> concatMap (ins 1 [[2,3]]) 

<interactive>:1:11: 
    Couldn't match expected type `a -> [b]' 
      against inferred type `[[[t]]]' 
    In the first argument of `concatMap', namely `(ins 1 [[2, 3]])' 
    In the expression: concatMap (ins 1 [[2, 3]]) 
    In the definition of `it': it = concatMap (ins 1 [[2, 3]]) 

Điều gì!?! Tại sao? OK, tôi kiểm tra chữ ký concatMap, và thấy rằng nó cần một lambda và một danh sách, nhưng đó là chỉ là một suy nghĩ của con người; GHC đối phó như thế nào? Theo định nghĩa của DOT trên ...

(f.g)x = f(g x), 

... những gì tôi đã làm là hợp lệ, thay thế khôn ngoan:

(concatMap . ins) x y = concatMap (ins x y) 

gãi đầu ...

*Main> concatMap (ins 1) [[2,3]] 
[[1,2,3],[2,1,3],[2,3,1]] 

Vì vậy, ...Các DOT lời giải thích rõ ràng là quá đơn giản ... DOT phải bằng cách nào đó đủ thông minh để hiểu rằng chúng ta trên thực tế muốn "in" để có được curri-ed đi và "ăn" các số đầu tiên - do đó trở thành một chức năng mà chỉ muốn để hoạt động trên [t] (và "xen kẽ" chúng với '1' ở tất cả các vị trí có thể).

Nhưng điều này được chỉ định ở đâu? Làm thế nào mà GHC biết để làm điều này, khi chúng tôi gọi:

*Main> (concatMap . ins) 1 [[2,3]] 
[[1,2,3],[2,1,3],[2,3,1]] 

Chữ ký "ins" bằng cách nào đó đã truyền đạt điều này ... "ăn chính sách đầu tiên của tôi"?

*Main> :info ins 
ins :: t -> [t] -> [[t]]  -- Defined at b.hs:1:0-2 

Tôi không thấy có gì đặc biệt - "in" là một chức năng mà phải mất một 't', một danh sách các 't', và tiền thu được để tạo ra một danh sách tất cả "interspersals". Không có gì về "ăn lập luận đầu tiên của bạn và cà ri nó đi".

Vì vậy, có ... Tôi đang bối rối. Tôi hiểu (sau một giờ xem mã!) Những gì diễn ra, nhưng ... Đức Chúa Trời toàn năng ... Có lẽ GHC cố gắng để xem có bao nhiêu lý lẽ nó có thể "bóc vỏ"?

let's try with no argument "curried" into "ins", 
    oh gosh, boom, 
    let's try with one argument "curried" into "ins", 
    yep, works, 
    that must be it, proceed) 

Again - yikes ...

Và vì tôi luôn so sánh các ngôn ngữ tôi đang học với những gì tôi đã biết, làm thế nào sẽ "in" nhìn bằng Python?

a=[2,3] 
print [a[:x]+[1]+a[x:] for x in xrange(len(a)+1)] 

[[1, 2, 3], [2, 1, 3], [2, 3, 1]] 

Hãy trung thực, bây giờ ... đơn giản hơn? Tôi có nghĩa là, tôi biết tôi là một newbie trong Haskell, nhưng tôi cảm thấy như một thằng ngốc ... Nhìn vào 4 dòng mã trong một giờ, và kết thúc lên giả định rằng trình biên dịch ... cố gắng giải thích khác nhau cho đến khi nó tìm thấy cái gì đó "nhấp chuột"?

Để trích dẫn từ vũ khí Lethal, "Tôi quá già cho điều này" ...

Answer 1

(f . g) x = f (g x) 

Điều này đúng. Bạn đã kết luận rằng:

(f . g) x y = f (g x y) 

cũng phải đúng, nhưng không phải như vậy. Thực tế, những điều sau đây là đúng:

(f . g) x y = f (g x) y 

không giống nhau.

Tại sao điều này đúng? Vâng (f . g) x y cũng giống như ((f . g) x) y và kể từ khi chúng ta biết rằng (f . g) x = f (g x) chúng ta có thể giảm đến (f (g x)) y, mà là một lần nữa giống như f (g x) y.

Vì vậy, (concatMap . ins) 1 [[2,3]] tương đương với concatMap (ins 1) [[2,3]]. Không có ma thuật nào xảy ra ở đây.

Một cách khác để tiếp cận này là thông qua các loại:

. có loại (b -> c) -> (a -> b) -> a -> c, concatMap có loại (x -> [y]) -> [x] -> [y], ins có loại t -> [t] -> [[t]].Vì vậy, nếu chúng ta sử dụng concatMap như là đối số b -> c và ins như là đối số a -> b, sau đó trở thành at, b trở thành [t] -> [[t]] và c trở thành [[t]] -> [[t]] (với x = [t] và y = [t]).

Vì vậy, loại concatMap . ins là t -> [[t]] -> [[t]], có nghĩa là một chức năng lấy bất kỳ danh sách danh sách nào (của người nổi tiếng) và trả về danh sách danh sách (cùng loại).

Answer 2

Tôi muốn thêm hai xu của mình. Các câu hỏi và trả lời làm cho nó âm thanh như . là một số nhà điều hành huyền diệu mà những điều kỳ lạ với sắp xếp lại các cuộc gọi chức năng. Đó không phải là trường hợp. . chỉ là thành phần chức năng. Dưới đây là một thực hiện bằng Python:

def dot(f, g): 
    def result(arg): 
     return f(g(arg)) 
    return result 

Nó chỉ tạo ra một chức năng mới mà áp dụng g để cãi nhau, áp dụng f đến kết quả, và trả về kết quả của việc áp dụng f.

Vì vậy, (concatMap . ins) 1 [[2, 3]] đang nói: tạo hàm, concatMap . ins và áp dụng hàm đó cho các đối số 1 và [[2, 3]]. Khi bạn thực hiện concatMap (ins 1 [[2,3]]), thay vào đó, hãy áp dụng hàm concatMap cho kết quả của việc áp dụng ins đến 1 và [[2, 3]] - hoàn toàn khác, như bạn đã tìm ra thông báo lỗi khủng khiếp của Haskell.

CẬP NHẬT: Để nhấn mạnh điều này hơn nữa. Bạn nói rằng (f . g) x là một cú pháp khác cho f (g x). Đây là sai! . chỉ là một hàm, vì các hàm có thể có tên không phải là số alpha (>><, .., v.v., cũng có thể là tên hàm).

Answer 3

Bạn đang khắc phục sự cố này. Bạn có thể làm việc tất cả bằng cách sử dụng lý luận equational đơn giản.Hãy thử nó từ đầu:

permute = foldr (concatMap . ins) [[]] 

Điều này có thể được chuyển đổi trivially để:

permute lst = foldr (concatMap . ins) [[]] lst 

concatMap có thể được định nghĩa là:

concatMap f lst = concat (map f lst) 

Cách foldr công trình trên một danh sách là (ví dụ):

-- let lst = [x, y, z] 
foldr f init lst 
= foldr f init [x, y, z] 
= foldr f init (x : y : z : []) 
= f x (f y (f z init)) 

Vì vậy, một cái gì đó giống như

permute [1, 2, 3] 

trở thành:

foldr (concatMap . ins) [[]] [1, 2, 3] 
= (concatMap . ins) 1 
    ((concatMap . ins) 2 
     ((concatMap . ins) 3 [[]])) 

Hãy làm việc thông qua các biểu hiện đầu tiên:

(concatMap . ins) 3 [[]] 
= (\x -> concatMap (ins x)) 3 [[]] -- definition of (.) 
= (concatMap (ins 3)) [[]] 
= concatMap (ins 3) [[]]  -- parens are unnecessary 
= concat (map (ins 3) [[]]) -- definition of concatMap 

Bây giờ ins 3 [] == [3], vì vậy

map (ins 3) [[]] == (ins 3 []) : [] -- definition of map 
= [3] : [] 
= [[3]] 

Vì vậy, biểu hiện ban đầu của chúng tôi trở thành:

foldr (concatMap . ins) [[]] [1, 2, 3] 
= (concatMap . ins) 1 
    ((concatMap . ins) 2 
     ((concatMap . ins) 3 [[]])) 
= (concatMap . ins) 1 
    ((concatMap . ins) 2 [[3]] 

Hãy làm việc thông qua

(concatMap . ins) 2 [[3]] 
= (\x -> concatMap (ins x)) 2 [[3]] 
= (concatMap (ins 2)) [[3]] 
= concatMap (ins 2) [[3]]  -- parens are unnecessary 
= concat (map (ins 2) [[3]]) -- definition of concatMap 
= concat (ins 2 [3] : []) 
= concat ([[2, 3], [3, 2]] : []) 
= concat [[[2, 3], [3, 2]]] 
= [[2, 3], [3, 2]] 

Vì vậy, biểu hiện ban đầu của chúng tôi trở thành:

foldr (concatMap . ins) [[]] [1, 2, 3] 
= (concatMap . ins) 1 [[2, 3], [3, 2]] 
= (\x -> concatMap (ins x)) 1 [[2, 3], [3, 2]] 
= concatMap (ins 1) [[2, 3], [3, 2]] 
= concat (map (ins 1) [[2, 3], [3, 2]]) 
= concat [ins 1 [2, 3], ins 1 [3, 2]] -- definition of map 
= concat [[[1, 2, 3], [2, 1, 3], [2, 3, 1]], 
      [[1, 3, 2], [3, 1, 2], [3, 2, 1]]] -- defn of ins 
= [[1, 2, 3], [2, 1, 3], [2, 3, 1], 
    [1, 3, 2], [3, 1, 2], [3, 2, 1]] 

Không có gì huyền diệu ở đây. Tôi nghĩ rằng bạn có thể đã bị nhầm lẫn bởi vì nó dễ dàng để giả định rằng concatMap = concat . map, nhưng điều này không phải là trường hợp. Tương tự, nó có thể giống như concatMap f = concat . (map f), nhưng điều này cũng không đúng. Lý luận bình đẳng sẽ cho bạn thấy lý do tại sao.