Тест Haskell: простая функция

Question

Я не программист Haskell, но мне любопытно ответить на следующие вопросы.

Неформальная функция спецификация:

Пусть MapProduct функция, которая принимает функцию с именем F и несколько списков. Он возвращает список, содержащий результаты вызова F с одним аргументом из каждого списка в каждой возможной комбинации.

Пример:

Вызов MapProduct с F является функцией, которая просто возвращает список своих аргументов, и два списка. Один из списков содержит целые числа 1 и 2, а другой содержит строки «a» и «b». Он должен вернуть список, содержащий списки: 1 и «a», 1 и «b», 2 и «a», 2 и «b».

Вопросы:

• Как реализуется MapProduct?
• Каков тип функции? Что такое тип F?
• Можно ли догадаться, что делает функция, просто глядя на ее тип?
• Можете ли вы обрабатывать неоднородные списки в качестве входных данных? (например, 1 и «a» в одном из списков ввода)
• Какое дополнительное ограничение (если оно имеется) необходимо ввести для реализации MapProduct?

Answer 1

• Как реализуется MapProduct?

.

Prelude> :m + Control.Applicative 
Prelude Control.Applicative> (,,) <$> [1,2,3] <*> ["a","b","c"] <*> [0.8, 1.2, 4.4] 
[(1,"a",0.8),(1,"a",1.2),...,(3,"c",4.4)] 

• Что такое тип работы функции? Что такое тип F?

Тип F зависит от списка, который вы хотите применить. <$> здесь fmap и (<*>) :: f(a->b) -> f a -> f b где f = [] здесь.

• Можете ли вы обрабатывать неоднородные списки в качестве входных данных? (Например, 1 и «а» в одном из входных списков)

Там нет такого понятия, как гетерогенных списка. Но вы можете simulate a heterogeneous list for a specific context with existential types. И тогда вы можете просто использовать метод выше для создания MapProduct.

*Main Control.Applicative> :i SB 
data ShowBox where 
    SB :: forall s. (Show s) => s -> ShowBox 
    -- Defined at v.hs:1:35-36 
*Main Control.Applicative> [SB 2, SB "a", SB 6.4] 
[2,"a",6.4] 
*Main Control.Applicative> (,) <$> [SB 2, SB "a", SB 6.4] <*> [SB 'z', SB 44] 
[(2,'z'),(2,44),("a",'z'),("a",44),(6.4,'z'),(6.4,44)] 

Answer 2

Функция, которую вы описываете, тесно связана с функциями zipWithN. Он будет иметь тот же тип - он просто приведет к большим спискам результатов. Теперь проблема заключается в том, что нет способа выразить «функцию, которая принимает N аргументов типов t_1, ..., t_n» или «n списков типов [t_1],...,[t_n]» (или «n-кортеж типа ([t_1], ..., [t_n]")) в системе типа haskell (без расширений . как шаблон Haskell) Вот почему не одна функция zipWith, но один для каждого числа списков аргументов, которые поддерживаются

Так, чтобы ответить на ваши вопросы:.

• Он реализуется путем определения function mapProductN для каждого числа N, которое вы хотите поддержать. Для N = 2 это будет выглядеть так:

  mapProduct f l1 l2 = [f x1 x2 | x1 <- l1, x2 <- x2] 
  

  Или как общий план (т. псевдо-код), как определить функции для любого N:

  mapProduct f l1 ... ln = [f x1 ... xn | x1 <- l1, ..., xn <- ln] 
  

• Как я уже сказал, что это так же, как типы функций zipWith, а именно:

  zipWith :: (a -> b -> c) -> [a] -> [b] -> [c] 
  zipWith3 :: (a -> b -> c -> d) -> [a] -> [b] -> [c] -> [d] 
  zipWith4 :: (a -> b -> c -> d -> e) -> [a] -> [b] -> [c] -> [d] -> [e] 
  

  Поскольку F является первым аргументом к функции, тип первого аргумента - тип f (поэтому для n = 2 это будет a -> b -> c)

• Ну, так как он имеет тот же тип, что и zipWith и zipWith делает что-то еще, это будет нет.

• Haskell не допускает неоднородных списков без расширения.

• Существует верхний предел количества списков, если вы не хотите тратить время на создание бесконечных версий mapProduct.

Answer 3

Это является можно определить функцию mapProduct, которая работает для любой арности функции:

{-# LANGUAGE FlexibleInstances, TypeFamilies #-} 

module MapProduct (
    mapProduct 
    ) where 

import Control.Monad 

newtype ProdFuncList a b = ProdFuncList [ a -> b ] 


class MapProdResult p where 
    type MapProdArg p 
    apNext :: ProdFuncList x (MapProdArg p) -> [x] -> p 

instance (MapProdResult b) => MapProdResult ([a] -> b) where 
    type MapProdArg ([a] -> b) = (a -> MapProdArg b) 
    apNext (ProdFuncList fs) = apNext . ProdFuncList . ap fs 

instance MapProdResult [b] where 
    type MapProdArg [b] = b 
    apNext (ProdFuncList fs) = ap fs 


mapProduct :: (MapProdResult q) => (a -> MapProdArg q) -> [a] -> q 
mapProduct f = apNext (ProdFuncList [f]) 

Вот она в действии:

> :l MapProduct.hs 
[1 of 1] Compiling MapProduct  (MapProduct.hs, interpreted) 
Ok, modules loaded: MapProduct. 
> mapProduct (+10) [1..4] :: [Int] 
[11,12,13,14] 
> mapProduct (*) [1..4] [10..12] :: [Int] 
[10,11,12,20,22,24,30,33,36,40,44,48] 
> mapProduct (\a b c -> a:b:c:[]) "bcs" "ao" "dnt" :: [String] 
["bad","ban","bat","bod","bon","bot","cad","can","cat","cod","con","cot","sad","san","sat","sod","son","sot"] 

Недостаток этого подход что вам, скорее всего, придется вводить аннотацию результата (как показано в приведенных выше примерах). Было бы гораздо более идиоматических просто использовать fmap и ap непосредственно:

> :m + Control.Monad 
> (+10) `fmap` [1..4] 
[11,12,13,14] 
> (*) `fmap` [1..4] `ap` [10..12] 
[10,11,12,20,22,24,30,33,36,40,44,48] 
> (\a b c -> a:b:c:[]) `fmap` "bcs" `ap` "ao" `ap` "dnt" 
["bad","ban","bat","bod","bon","bot","cad","can","cat","cod","con","cot","sad","san","sat","sod","son","sot"] 

Это не требует аннотации типа, а полностью вообще на все монады, а не только [].

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