Mapowanie heterogenicznej struktury danych z ogólną funkcją

Question

Pracuję nad implementacją HList i utknąłem próbując zaimplementować dla niej funkcję map. Próbowałem wielu różnych podejść, ale z każdym z nich dochodzę do błędów kompilatora związanych z tą funkcją.

Poniżej przedstawiono przykład użycia ogólnej funkcji Just w celu zastosowania jej do wszystkich elementów struktury danych wejściowych.

{-# 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 

Mając to ja otrzymuję następujący błąd kompilatora:

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

Czy istnieje w ogóle taki sposób, aby rozwiązać ten problem, a jeśli nie, to dlaczego?

Answer 1

Problem polega na tym, że próbujesz użyć funkcji polimorficznej z różnymi argumentami, ale instancja Apply przyjmuje funkcję (typ mono). Można łatwo naprawić wiele sposobów

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

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

współpracuje z kodem dobrze

EDIT: bardziej ogólne podejście do tej samej rzeczy jest (wymagające 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 

lub jeśli jesteś przy użyciu najnowszej wersji GHC i chętniej włączyć więcej rozszerzeń

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 

co jest miłe od tego czasu pozwala ci robić rzeczy takie jak "show" w funkcji, którą mapujesz.

Aby uzyskać bardziej ogólne rozwiązanie, należy sprawdzić kod Oleg's Type level lambda caclulus, który umożliwia wpisanie kodu na poziomie wartości, a następnie automatyczne wypełnienie odpowiedniego programu poziomu. Niestety, rozwiązanie Olega jest w tym momencie dość stare i wykorzystuje nominalną implementację LC, której nie lubię szczególnie. Zastanawiałem się, jak to zrobić lepiej, ale może wytrzymać, dopóki nie dojdzie do racjonalnej równości, by wpisać rodziny.

Moim zdaniem HLists powinno być wykonywane w tych dniach przy użyciu GADT i DataKinds zamiast krotek. Rodziny typu są lepsze od zależności funkcjonalnych, ale obecnie są bardziej ograniczone, ponieważ nie mają decydującej równości.

Answer 2

Chociaż następujący nie dokładnie odpowiedzieć na pytanie (tak, nie będę jej przyjęciem), to nie rozwiązuje problemu dotyczącego odwzorowywania struktury bez konieczności żadnych dodatkowych wystąpień dla aplikacyjnych funktorów:

{-# 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) 

Wyjścia :

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