Lập bản đồ qua cấu trúc dữ liệu không đồng nhất với chức năng chung

Question

Tôi đang thực hiện triển khai HList và tôi đang cố gắng triển khai hàm map cho nó. Tôi đã thử nhiều cách tiếp cận khác nhau nhưng với mỗi phương pháp tôi gặp phải lỗi trình biên dịch liên quan đến hàm đó.

Sau đây là ví dụ về cách tôi muốn sử dụng hàm chung Just để áp dụng cho tất cả các phần tử của cấu trúc dữ liệu đầu vào.

{-# LANGUAGE MultiParamTypeClasses #-} 
{-# LANGUAGE FlexibleInstances #-} 

-- | An input heterogenous data structure 
recursivePairs :: (Int, (Char, (Bool,()))) 
recursivePairs = (1, ('a', (True,()))) 

-- | This is how I want to use it 
recursivePairs' :: (Maybe Int, (Maybe Char, (Maybe Bool,()))) 
recursivePairs' = hMap Just recursivePairs 

class HMap f input output where 
    hMap :: f -> input -> output 

-- | A counterpart of a Nil pattern match for a list 
instance HMap f()() where 
    hMap _ _ =() 

-- | A counterpart of a Cons pattern match for a list 
instance 
    (HMap f iTail oTail, 
    Apply f iHead oHead) => 
    HMap f (iHead, iTail) (oHead, oTail) 
    where 
    hMap f (head, tail) = (apply f head, hMap f tail) 

class Apply f input output where 
    apply :: f -> input -> output 

instance Apply (input -> output) input output where 
    apply = id 

Với điều này tôi nhận ra lỗi biên dịch sau:

No instance for (Apply (a0 -> Maybe a0) Int (Maybe Int)) 
    arising from a use of `hMap' 
The type variable `a0' is ambiguous 

Có ở tất cả một cách để giải quyết việc này và nếu không thì tại sao?

Answer 1

Vấn đề là bạn đang cố sử dụng chức năng đa hình với các đối số khác nhau, nhưng cá thể Apply của bạn có chức năng (kiểu đơn). Bạn có thể dễ dàng sửa lỗi này nhiều cách

data JustIfy = JustIfy 
instance Apply JustIfy a (Maybe a) where 
    apply _ = Just 

recursivePairs' :: (Maybe Int, (Maybe Char, (Maybe Bool,()))) 
recursivePairs' = hMap JustIfy recursivePairs 

công trình với mã của bạn tốt

EDIT: Một cách tiếp cận tổng quát hơn để điều tương tự được (đòi hỏi RankNTypes)

--A "universal" action that works on all types 
newtype Univ f = Univ (forall x. x -> f x) 
instance Apply (Univ f) x (f x) where 
    apply (Univ f) x = f x 

recursivePairs' :: (Maybe Int, (Maybe Char, (Maybe Bool,()))) 
recursivePairs' = hMap (Univ Just) recursivePairs 

hoặc nếu bạn là sử dụng phiên bản mới nhất của GHC và sẵn sàng bật nhiều tiện ích mở rộng hơn

newtype Univ' c f = Univ' (forall x. c x => x -> f x) 
instance c x => Apply (Univ' c f) x (f x) where 
    apply (Univ' f) x = f x 

class All x 
instance All x 

recursivePairs' :: (Maybe Int, (Maybe Char, (Maybe Bool,()))) 
recursivePairs' = hMap (Univ' Just :: Univ' All Maybe) recursivePairs 

là tốt đẹp kể từ đó nó cho phép bạn làm những việc như bao gồm một "hiển thị" trong chức năng bạn bản đồ với.

Để có giải pháp tổng quát hơn, hãy xem Oleg's Type level lambda caclulus cho phép bạn viết mã ở cấp giá trị và sau đó tự động nhập chương trình cấp thích hợp. Thật không may, giải pháp của Oleg là vào thời điểm này khá cũ, và sử dụng một thực hiện danh nghĩa của LC mà tôi không đặc biệt thích. Tôi đã suy nghĩ về việc làm thế nào để làm tốt hơn, nhưng có thể giữ cho đến khi sự bình đẳng đáng kể đến với các gia đình thuộc loại.

Quan điểm của tôi là những người theo đạo Hồi nên thực hiện những ngày này bằng cách sử dụng GADT và DataKinds chứ không phải là bộ dữ liệu. Loại gia đình thích hợp hơn với các phụ thuộc chức năng, nhưng hiện tại bị giới hạn hơn bởi vì chúng thiếu sự bình đẳng đáng tin cậy.

Answer 2

Mặc dù sau đây không chính xác trả lời câu hỏi (vì vậy tôi sẽ không được chấp nhận nó), nó không giải quyết vấn đề liên quan đến việc lập bản đồ cấu trúc mà không đòi hỏi bất kỳ phiên bản bổ sung cho functors applicative:

{-# LANGUAGE MultiParamTypeClasses #-} 
{-# LANGUAGE FlexibleInstances #-} 

import Control.Applicative 

main = do 
    print $ (hPure recursivePairs :: (Maybe Int, (Maybe Char, (Maybe Bool,())))) 
    print $ (hPure recursivePairs :: ([Int], ([Char], ([Bool],())))) 

recursivePairs :: (Int, (Char, (Bool,()))) 
recursivePairs = (1, ('a', (True,()))) 

class HPure input output where 
    hPure :: input -> output 

instance HPure()() where 
    hPure _ =() 

instance 
    (Applicative f, 
    HPure iTail oTail) => 
    HPure (iHead, iTail) (f iHead, oTail) 
    where hPure (iHead, iTail) = (pure iHead, hPure iTail) 

đầu ra :

(Just 1,(Just 'a',(Just True,()))) 
([1],("a",([True],())))