Как я могу абстрагировать общий рекурсивный аппликативный шаблон функтора на Haskell?

Question

При использовании аппликативных функторов в Haskell я часто сталкиваюсь с ситуациями, когда я получаю повторяющийся код, подобный этому:

instance Arbitrary MyType where
  arbitrary = MyType <$> arbitrary <*> arbitrary <*> arbitrary <*> arbitrary

В этом примере я хотел бы сказать:

instance Arbitrary MyType where
  arbitrary = applyMany MyType 4 arbitrary

но я не могу понять, как сделать applyMany (или что-то подобное). Я даже не могу понять, каким будет тип, но для этого потребуется конструктор данных, Int (n) и функция, которую нужно n применить. Это происходит при создании экземпляров для QuickCheck, SmallCheck, Data.Binary, сериализации Xml и других рекурсивных ситуаций.

Так как я могу определить applyMany?

Answer 1

Проверить получить . Любая другая хорошая универсальная библиотека должна быть в состоянии сделать это; производная - только тот, с кем я знаком. Например:

{-# LANGUAGE TemplateHaskell #-}
import Data.DeriveTH
import Test.QuickCheck

$( derive makeArbitrary ''MyType )

Чтобы ответить на вопрос, который вы фактически задали, FUZxxl прав, это невозможно в простом ванильном Хаскеле. Как вы указываете, неясно, каким должен быть его тип. Это возможно с метапрограммированием Template Haskell (не слишком приятно). Если вы пойдете по этому пути, вы, вероятно, должны просто использовать универсальную библиотеку, которая уже провела для вас тяжелые исследования. Я полагаю, что это также возможно с использованием натуралов и классов типов на уровне типов, но, к сожалению, такие решения на уровне типов обычно трудно абстрагировать. Конор МакБрайд работает над этой проблемой .

Answer 2

Я думаю, что вы можете сделать это с помощью взлома OverlappingInstances:

{-# LANGUAGE FlexibleInstances, MultiParamTypeClasses, TypeFamilies, OverlappingInstances #-}
import Test.QuickCheck
import Control.Applicative


class Arbitrable a b where
    convert :: Gen a -> Gen b

instance (Arbitrary a, Arbitrable b c) => Arbitrable (a->b) c where
    convert a = convert (a <*> arbitrary)

instance (a ~ b) => Arbitrable a b where
    convert = id

-- Should work for any type with Arbitrary parameters
data MyType a b c d = MyType a b c d deriving (Show, Eq)

instance Arbitrary (MyType Char Int Double Bool) where
    arbitrary = convert (pure MyType)

check = quickCheck ((\s -> s == s) :: (MyType Char Int Double Bool -> Bool))

Answer 3

Не удовлетворен другим моим ответом, я придумал потрясающий.

-- arb.hs
import Test.QuickCheck
import Control.Monad (liftM)

data SimpleType = SimpleType Int Char Bool String deriving(Show, Eq)
uncurry4 f (a,b,c,d) = f a b c d

instance Arbitrary SimpleType where
    arbitrary = uncurry4 SimpleType `liftM` arbitrary
    -- ^ this line is teh pwnzors.
    --  Note how easily it can be adapted to other "simple" data types

---

ghci> :l arb.hs
[1 of 1] Compiling Main             ( arb.hs, interpreted )
Ok, modules loaded: Main.
ghci> sample (arbitrary :: Gen SimpleType)
>>>a bunch of "Loading package" statements<<<
SimpleType 1 'B' False ""
SimpleType 0 '\n' True ""
SimpleType 0 '\186' False "\208! \227"
...

Длительное объяснение того, как я понял это

Так вот как я понял.Мне было интересно, "ну как же уже существует экземпляр Arbitrary для (Int, Int, Int, Int)? Я уверен, что никто не написал его, так что он должен быть как-то получен. Конечно, я нашел следующее в документы для экземпляров Arbitrary :

(Arbitrary a, Arbitrary b, Arbitrary c, Arbitrary d) => Arbitrary (a, b, c, d)

Хорошо, если они уже определили это, то почему бы не злоупотреблять им? Простые типы, которые просто составлены из меньших произвольных типов данных, не являютсясильно отличается от просто кортежа.

Так что теперь мне нужно каким-то образом преобразовать «произвольный» метод для 4-кортежа, чтобы он работал для моего типа. Вероятно, задействовано нерегулярное выполнение.

StopHoogle time!

(Мы можем легко определить наш собственный uncurry4, поэтому предположим, что у нас уже есть это для работы.)

У меня есть генератор, arbitrary :: Gen (q,r,s,t) (где q,r, s, t - все случаи Произвольного). Но давайте просто скажем, что это arbitrary :: Gen a. Другими словами, a представляет (q,r,s,t). У меня есть функция uncurry4, которая имеет тип (q -> r -> s -> t -> b) -> (q,r,s,t) -> b. Мыочевидно, что мы будем применять uncurry4 к нашему конструктору SimpleType, поэтому uncurry4 SimpleType имеетpe (q,r,s,t) -> SimpleType.Давайте оставим возвращаемое значение общим, потому что Hoogle не знает о нашем SimpleType.Итак, помня наше определение a, мы имеем по существу uncurry4 SimpleType :: a -> b.

Итак, у меня есть Gen a и функция a -> b.И я хочу Gen b результат.(Помните, что для нашей ситуации a - это (q,r,s,t), а b - это SimpleType).Поэтому я ищу функцию с сигнатурой этого типа: Gen a -> (a -> b) -> Gen b. Обдумав это и зная, что Gen является экземпляром Monad, я сразу же распознаю liftM как монадическое магическое решение моих проблем.

Google снова спасает день,Я знал, что, возможно, был какой-то «подъёмный» комбинатор, чтобы получить желаемый результат, но я, честно говоря, не думал использовать liftM (durrr!), Пока не набрал подпись типа.

Answer 4

Вот что я получил по крайней мере:

{-# LANGUAGE TypeFamilies, MultiParamTypeClasses, FlexibleInstances #-}
{-# LANGUAGE FlexibleContexts #-}

module ApplyMany where

import Control.Applicative
import TypeLevel.NaturalNumber -- from type-level-natural-number package

class GetVal a where
  getVal :: a

class Applicative f => ApplyMany n f g where
  type Res n g
  app :: n -> f g -> f (Res n g)

instance Applicative f => ApplyMany Zero f g where
  type Res Zero g = g
  app _ fg = fg

instance
  (Applicative f, GetVal (f a), ApplyMany n f g)
  => ApplyMany (SuccessorTo n) f (a -> g)
  where
    type Res (SuccessorTo n) (a -> g) = Res n g
    app n fg = app (predecessorOf n) (fg<*>getVal)

Пример использования:

import Test.QuickCheck

data MyType = MyType Char Int Bool deriving Show
instance Arbitrary a => GetVal (Gen a) where getVal = arbitrary

test3 = app n3 (pure MyType) :: Gen MyType
test2 = app n2 (pure MyType) :: Gen (Bool -> MyType)
test1 = app n1 (pure MyType) :: Gen (Int -> Bool -> MyType)
test0 = app n0 (pure MyType) :: Gen (Char -> Int -> Bool -> MyType)

Кстати, я думаю, что это решение не очень полезно в реальном мире.Особенно без местных типов классов.

Answer 5

Выезд ЛифтА2 и ЛифтА3 .Кроме того, вы можете легко написать свои собственные методы applyTwice или applyThrice, например так:

applyTwice :: (a -> a -> b) -> a -> b
applyTwice f x = f x x

applyThrice :: (a -> a -> a -> b) -> a -> b
applyThrice f x = f x x x

Нет простого способа получить общий запрос applyMany, о котором вы просите, но написать тривиальные помощники, подобные этимни сложно, ни необычно.

---

[править] Получается, что вы думаете, что-то вроде этого будет работать

liftA4 f a b c d = f <$> a <*> b <*> c <*> d
quadraApply f x = f x x x x

data MyType = MyType Int String Double Char

instance Arbitrary MyType where
    arbitrary = (liftA4 MyType) `quadraApply` arbitrary

Но это не так.(liftA4 MyType) имеет сигнатуру типа (Applicative f) => f Int -> f String -> f Double -> f Char -> f MyType.Это несовместимо с первым параметром quadraApply, который имеет сигнатуру типа (a -> a -> a -> a -> b) -> a -> b.Это будет работать только для структур данных, которые содержат несколько значений одного и того же произвольного типа.

data FourOf a = FourOf a a a a

instance (Arbitrary a) => Arbitrary (FourOf a) where
    arbitrary = (liftA4 FourOf) `quadraApply` arbitrary

ghci> sample (arbitrary :: Gen (FourOf Int))

Конечно, вы можете просто сделать это, если у вас есть такая ситуация

ghci> :l +Control.Monad
ghci> let uncurry4 f (a, b, c, d) = f a b c d
ghci> samples <- sample (arbitrary :: Gen (Int, Int, Int, Int))
ghci> forM_ samples (print . uncurry4 FourOf)

Возможно,некоторая языковая прагма, которая может включить «произвольную» функцию в более разнообразные типы данных.Но это в настоящее время выше моего уровня Хаскелл-фу.

Answer 6

Это невозможно с Haskell. Проблема в том, что ваша функция будет иметь тип, который зависит от числового аргумента. С системой типов, которая допускает зависимые типы, это должно быть возможно, но я не думаю, что в Haskell.

То, что вы можете попробовать, это использовать полиморфизм и классы классов для архивирования этого, но это может стать хакерским, и вам понадобится большой набор расширений, чтобы удовлетворить компилятор.