2011-09-19 34 views
6

Vì vậy, tôi đang chơi xung quanh với điều này:Bắt một giá trị kiểu Integral a => [a] từ một giá trị của một Integral => ([a], [a], [a])

factors :: Integral a => a -> [a] 
factors n = filter (\d -> n `rem` d == 0) . takeWhile (\d -> d*d <= n) $ [ 1 .. ] 

abundants_perfects_deficients :: Integral a => ([a],[a],[a]) 
abundants_perfects_deficients = foldr switch ([],[],[]) [1..] 
    where switch :: Integral a => a -> ([a],[a],[a]) -> ([a],[a],[a]) 
     switch n (as,ps,ds) = 
      let t = sum (factors n) in 
       if t < n then (as,ps,n:ds) 
      else if t == n then (as,n:ps,ds) 
      else     (n:as,ps,ds) 

Và trong khi tôi có abundants_perfects_deficients, tôi muốn có ba giá trị: abundants, perfectsdeficients tất cả các loại Integral a -> [a].

Một điều đó không làm việc là:

abundants,perfects,deficients :: Integral a => [a] 
(abundants,perfects,deficients) = abundants_perfects_deficients 

Bởi vì đây chế các ba cho tất cả được so với cùng a.

tôi đã cố gắng một cái gì đó để làm cho họ một-by-một, vì vậy họ sẽ không lẫn nhau hạn chế, nhưng điều đó không làm việc, hoặc:

perfects :: Integral a => [a] 
(_,perfects,_) = abundants_perfects_deficients 

Bởi vì trình biên dịch không thể tìm ra cách để chuyển đổi giá trị loại forall a. Integral a => ([a],[a],[a]) để nhập (t1, forall a. Integral a => [a], t2).

Điều đó có vẻ đủ sắc sảo.

Bây giờ tôi biết tôi có thể thực hiện chúng một cách riêng biệt (chỉ perfects = filter isPerfect [1..]), hoặc hạn chế chúng để tất cả có cùng loại ((abundants,perfects,deficients) = abundants_perfects_deficients hoạt động tốt nếu abundants,perfects,deficients :: [Integer]), nhưng

  • Tôi thích sử dụng chia sẻ thông tin để xây dựng cả ba
  • tôi muốn không chỉ bị hạn chế để Integer s

ý tưởng?


Sửa: Fascinatingly đủ công trình này:

abundants :: Integral a => [a] 
abundants = f as 
    where as :: [Integer] 
     (as,_,_) = abundants_perfects_deficients 
     f :: Integral a => [Integer] -> [a] 
     f = map fromInteger 

Nhưng điều này không:

abundants_perfects_deficients' :: (Integral a,Integral p, Integral d) => ([a],[p],[d]) 
abundants_perfects_deficients' = (f as, f ps, f ds) 
    where as,ps,ds :: [Integer] 
     (as,ps,ds) = abundants_perfects_deficients 
     f :: Integral a => [Integer] -> [a] 
     f = map fromInteger 

abundants,perfects,deficients :: (Integral a) => [a] 
(abundants,perfects,deficients) = abundants_perfects_deficients' 

Tôi không có ý tưởng tại sao.

Trả lời

7

này liên quan đến những loại đa hình thực sự có ý nghĩa, đó là hơi phức tạp hơn như thế nào họ lần đầu tiên xuất hiện.

Tại thời điểm này nó có thể dễ dàng hơn để chuyển đổi chế độ suy nghĩ và nhìn vào lượng hóa như là một hình thức lambda trừu tượng: Một loại như ∀ a. [a] là như vậy, một hàm tham gia một đối số kiểu duy nhất, và trả về một danh sách của những thứ thuộc loại đó.Các ràng buộc lớp như Integral a có thể được xem như là các đối số bổ sung (cụ thể là từ điển cá thể) được cung cấp ngầm khi GHC tìm thấy các giá trị cho bạn.

Để nhấn mạnh điểm, tôi sẽ viết các số lượng như /\ a -> để bắt chước cú pháp lambda và viết các ràng buộc lớp làm đối số thông thường.

Được viết theo cách này, loại abundants_perfects_deficients/\a -> Integral a -> ([a],[a],[a]) và nỗ lực ban đầu của bạn không thành công vì bạn đang cố gắng khớp mẫu trên kết quả của hàm hai đối số. Trong nhiều trường hợp, GHC tự động xáo trộn các đối số ngầm định xung quanh để làm cho mọi thứ hoạt động, nhưng ở đây rõ ràng là không thể - để có được kết quả từ abundants_perfects_deficients trước tiên bạn cần áp dụng nó cho cả hai đối số, nhận được kết quả đơn hình. bị ràng buộc bằng cách sử dụng mẫu. Ngay cả khi mẫu chỉ liên kết một giá trị, phần còn lại là _, GHC vẫn cần phải kiểm tra kiểu tự ràng buộc mẫu, do đó, mặc dù có vẻ như các đối số thừa có thể được đưa ra khỏi mã định danh duy nhất, điều này không thành công lý do ràng buộc cả ba cùng một lúc.

Để liên kết ba giá trị đa hình với mẫu, thay vào đó bạn sẽ cần thêm đối số để ở bên trong, cho phép abundants_perfects_deficients loại như (/\a -> Integral a -> [a], /\a -> Integral a -> [a], /\a -> Integral a -> [a]). Điều này đòi hỏi the ImpredicativeTypes extension, trong đó có một quá khứ hơi ca rô, và mà tôi vẫn còn cảnh giác.

Rất nhiều điều bạn đang mắc phải ở đây là GHC không đủ thông minh để tìm ra những thứ "hiển nhiên", như kiểu ẩn ngầm và các đối số ràng buộc dựa trên chỉ được sử dụng trong một phần cụ thể của ràng buộc. Do có bao nhiêu phép thuật đã làm đằng sau hậu trường, điều này không làm phiền tôi quá nhiều. :]

Giải pháp đơn giản nhất là chỉ cần ràng buộc cả ba cách riêng biệt, sử dụng hàm chọn để trích xuất các phần tử riêng lẻ. Điều này cho phép ràng buộc mức cao nhất là đa hình theo cách mong đợi, với các đối số tiềm ẩn mà nó nhận được ngầm được truyền đến abundants_perfects_deficients và chức năng chiếu đơn giản loại bỏ ba đối tượng khác sau một mẫu khớp (nay là đơn hình).

3
abundants,perfects,deficients :: Integral a => [a] 
(abundants,perfects,deficients) = abundants_perfects_deficients 

Hãy thử:

fst3 (a,_,_) = a 
snd3 (_,a,_) = a 
thd3 (_,_,a) = a 

abundants,perfects,deficients :: Integral a => [a] 
abundants = fst3 . abundants_perfects_deficients 
perfects = snd3 . abundants_perfects_deficients 
deficients = thd3 . abundants_perfects_deficients 
+0

sẽ không làm việc: 'fst :: (a, b) -> a' (và tương tự cho snd), bạn sẽ phải cung cấp một số truy cập ba-tuple mới;) –

+0

Ops, bạn nói đúng. Đã cập nhật để khắc phục. – nulvinge

+0

cần phải loại bỏ toán tử (.) Của bạn (abundants_perfects_deficients không phải là một hàm) – rampion

1

fromIntegral có thể có ích:

Prelude> :t fromIntegral 
fromIntegral :: (Num b, Integral a) => a -> b 
1

Có lẽ hơi ngoại cảm, nhưng dù sao đi nữa.

chức năng factors của bạn là sai (cố gắng tính toán factors 28;)

Dưới đây là một cách tiếp cận khác nhau cho vấn đề:

classifieds = map (\n -> (n, compare n (sum $ factors n))) [1..] 

perfects = map fst $ filter ((== EQ) . snd) classifieds 
abundants = map fst $ filter ((== GT) . snd) classifieds 
deficients = map fst $ filter ((== LT) . snd) classifieds 
+0

Rất tiếc :) những ý tưởng hay. – rampion

Các vấn đề liên quan