- PVSM.RU - https://www.pvsm.ru -
– А видела ты Черепаху «Как бы»?
– Нет, – сказала Алиса. – Я даже не знаю, кто это такой.
– Как же, – сказала Королева. – Это то, из чего делают «Как бы черепаший суп».
Льюис Кэрролл, «Алиса в Стране чудес»
— Судя по твоим речам, ты хорошо знаешь Фангорн? — спросил в ответ Арагорн.
— Какое там! — отозвался старик. — На это ста жизней не хватит. Но я сюда иной раз захаживаю.
Джон Р. Р. Толкиен, «Властелин Колец» — к слову о моём знании Haskell ;)
Homines dum docent, discunt. (Объясни другим — сам поймёшь.)
народная латинская поговорка
Все знают, что любая функция Haskell по своей сути является функцией одного параметра. Функции «как бы» нескольких параметров просто принимая первый аргумент, возвращают другую функцию, принимающую второй аргумент (исходной функции) и обратно возвращающую функцию и т.д. до финальной функции, которая уже возвращает значение не функционального типа (каррирование [1]).
Казалось бы о каком переменном числе параметров может идти речь при таком раскладе? Однако поразмыслив, посмотрев исходники printf [2] или просто почитав wiki.haskell [3] становится очевидным, что как раз ФП [4] даёт ключ к достаточно красивому, хотя и несколько «казуистическому» решению этой задачи.
В настоящей публикации я рассмотрю один из способов реализации такого механизма на простых примерах, а также предложу некоторое обобщённое решение на базе Template Haskell [5], для превращения семейства обычных функций с последним параметром типа список в функцию с «как бы с переменным числом параметром» (далее по тексту просто «с переменным числом параметром»).
Коротко опишу суть решения начиная с предельно простого примера.
{-# LANGUAGE FlexibleInstances, RankNTypes #-} -- (0)
class VarArgs a where prc :: String -> a -- (1)
instance VarArgs String where prc = id -- (2)
instance (Show a, VarArgs r) => VarArgs (a -> r) where -- (3)
prc acc = x -> prc $ acc ++ " " ++ show x
magic = prc []
useMagic :: (forall a. VarArgs a => a) -> IO () -- (4)
useMagic f = do
putStrLn $ magic 1
putStrLn $ magic 1 "qwe"
putStrLn $ magic 1 "qwe" [1, 2, 3]
main :: IO ()
main = do
putStrLn $ magic 1 2 "qwe" [1,2,3] 123.456
useMagic magic -- (5)
Что же здесь происходит и каким образом удаётся передать функции magic не только произвольное количество параметров, но к тому же параметры разных типов?
Итак в (1) мы объявляем класс VarArgs с единственным методом prc просто умеющим создать из строки значение заданного типа. Далее, в (2) мы реализуем экземпляр этого класса для типа String (также известного, как [Char]). Обратите внимание, что пришлось воспользоваться расширением FlexibleInstances (0) — иначе такой экземпляр будет «вне закона».
{-# LANGUAGE TypeFamilies #-}
instance a ~ Char => VarArgs [a] where prc = id
Экземпляр VarArgs String — это собственно и есть «тело» функции с переменным числом параметров. В примере мы просто возвращаем накопленные параметры. Теперь перейдём к самому интересному, в (3) мы объявляем экземпляр VarArgs для функционального типа (a -> r), при этом требуя, что бы тип аргумента a умел отображаться в строку, а тип результата r вновь принадлежал бы классу VarArgs.
Вот тут то «собака и порылась» — инстанцируя класс функциональным типом с типом возврата также допускающим (в частности) функцию мы позволяем методу prc в зависимости от контекста вызова возвращать как финальное значение типа String, если в контексте требуется строка, так и функцию, если тип результата вызова prc выводится из контекста как функциональный.
Теперь рассмотрим определение prc для экземпляра VarArgs (a -> r). Если вывести тип prc, то мы получим
prc :: (Show a, VarArgs r) => String -> (a -> r)
Т.е. мы должны вернуть функцию, что-то делающую с представимым в качестве строки значением. Аргумент acc это суть «накопитель» результата последовательной обработки параметров. В данном случае мы просто прибавляем к нему строковое представление параметра через пробел.
Важный момент в том, что мы не просто возвращаем приращённый «аккумулятор», но вызываем (в «теле» результирующей функции) рекурсивно prc чтобы получить требуемый тип результата r. Какая именно реализация prc будет вызвана (т.е. какой тип будет выведен) зависит от контекста (не забываем, что функции Haskell — это уравнения, а процесс вычисления — это последовательные подстановки выражений с актуализацией параметров).
Самое интересное, что несмотря на «полулегальный» статус мы вполне может передавать (4) и использовать (5) функцию с переменным числом параметров в качестве аргумента другой функции. Правда для этого нам пришлось использовать ещё одно расширение RankNTypes (0) и квантификатор forall в определении вызывающе функции (4).
Звучит немного запутанно, поэтому рассмотрим по шагам как вычисляется выражение справа от $ в (4):
обратной польской нотации [6]. Что-то наподобие:
> calcRPN 5 8 (*) 2 (+) -- 5*8 + 2
42
Максимально примитивная реализация может выглядеть как-то так:
{-# LANGUAGE ExtendedDefaultRules, FlexibleInstances, GADTs #-}
data Expr = Num Double | Op (Double -> Double -> Double)
calcRPN' :: [Expr] -> Double
calcRPN' = head . foldr rpnStep [] . reverse
rpnStep :: Expr -> [Double] -> [Double]
rpnStep (Num n) stack = n : stack
rpnStep (Op f) (x:y:stack) = (f x y) : stack
class ArgPrc a where
prc :: [Expr] -> a
class ArgSrc a where
toArg :: a -> Expr
instance ArgPrc Double where
prc = calcRPN' . reverse
instance (ArgSrc a, ArgPrc r) => ArgPrc (a -> r) where
prc acc = prc . (: acc) . toArg -- (2)
instance ArgSrc Expr where
toArg = id
instance a ~ Double => ArgSrc (a -> a -> a) where
toArg = Op
instance ArgSrc Integer where
toArg = Num . fromIntegral
instance ArgSrc String where
toArg = Num . fst . head . (reads :: ReadS Double)
instance ArgSrc [Double] where
toArg = Num . sum
calcRPN :: ArgPrc a => a
calcRPN = prc []
main = do
print $ calcRPN' [Num 5, Num 5, Op (*)]
print $ calcRPN [1::Double,2,3] "5" (*) 7 (*)
Схема реализации переменного числа параметров та же, что и в предыдущем примере, только теперь мы будем:
Наконец давайте рассмотрим схематический вариант реализации функции printf:
{-# LANGUAGE GADTs, FlexibleInstances, ExtendedDefaultRules #-}
type FmtRes = (String, String)
class PfVal a where
doFmt :: (String, String) -> a -> FmtRes
instance PfVal Integer where
doFmt (fmt, res) x =
let (b, s) = span (/= '%') fmt
in (res ++ (tail . tail $ s), b ++ show x)
instance PfVal String where
doFmt (fmt, res) x =
let (b, s) = span (/= '%') fmt
in (res ++ (tail . tail $ s), b ++ x)
class ArgProc a where
prc :: FmtRes -> a
instance ArgProc String where
prc = uncurry (++)
instance ArgProc (IO ()) where
prc = putStrLn . uncurry (++)
instance (PfVal a, ArgProc r) => ArgProc (a -> r) where
prc st = prc . doFmt st
printf fmt = prc (fmt, "")
main :: IO()
main = do
putStrLn $ printf "%d %s" 1 "qwe"
printf "%s %d" "This is" 123
Полагаю, код в особых комментариях не нуждается, отмечу только, что теперь мы снова генерируем результат «на лету», вместо накапливания параметров и реализуем два терминальных экземпляра класса ArgProc: для типа String и для типа IO ().
Если обобщить проиллюстрированную схему, то можно выделить следующие элементы:
A -> a -> A
class ArgProc a where
prc :: A -> a
instance (ArgSrc a, ArgProc r) ArgProc (a -> r) where
prc :: A -> (a -> r)
В примере с printf [8] накапливается сразу результат (второй элемент пары) и попутно обрабатывается состояние (строка формата). В примере с обратной польской нотацией [7] параметры просто складываются в список для последующей обработки.
instance ArgProc R1 where prc :: A -> R1
instance ArgProc R2 where prc :: A -> R2
...
В примере с обратной польской нотацией [7] присутствует всего один такой экземпляр для результирующего типа Double — он просто запускает вычисление для списка предварительно накопленных параметров. В примере с printf [8] экземпляр для String просто конкатенирует отформатированную строку с остатками формата (подразумевается, что там остался плоский текст). Экземпляр для IO () дополнительно выводит результат.
x -> (x, "") :: String -> (String -> String)
Нетрудно видеть, что такую схему можно воплотить в жизнь средствами «чёрной магии» Template Haskell [5]. Это неплохое упражнение для закрепления материала, а также хорошая площадка для плясок с бубном экспериментов с Template Haskell [5].
В текущей реализации я ограничился подмножеством общей схемы: накопитель — это просто список значений некоторого типа, инициализатор соответственно просто []. У таких ограничений есть конечно определённые минусы, но идея состоит в том, что бы превратить семейство обычных функций с идентичным типом параметров, последний из которых список, и различными типами возврата, в функцию, принимающую переменное число параметров (помимо фиксированных, идущих до списка).
Попутно автоматизируем процесс «неявного приведения» (в терминологии других ЯП) заданных типов к типу элементов списка параметров. Ещё одно ограничение — «донорские» функции должны иметь «простые» типы (не полиморфные типы без квантификаторов и ограничений).
Снова сразу начну с примеров использования, так будет понятна идея, а уже потом кратко пройдусь по реализации. Итак начнём с чего-нибудь простенького:
{-# LANGUAGE TemplateHaskell, FlexibleInstances, ExtendedDefaultRules #-}
import Data.Function.Vargs -- (1)
-- (2)
tester' q (x : y : z) =
putStrLn $ "Fixed parameter " ++ q ++ ", next x = " ++ x ++ " and y = " ++ y
++ " and rest = " ++ show z
$( return [] ) -- (3)
-- (4)
defVargsFun "tester" ['tester']
(''Integer, [| ("Int " ++) . show |]) -- (5)
(''(), [| const "NULL" |]) -- (6)
([t| [Int] |], [| ("[Int] " ++) . show |]) -- (7)
([t| [Double] |], [| ("[Double] " ++) . show |]) -- (8)
main :: IO ()
main = do
tester "<const>" "qwe" 100500 () [1::Int,2,3] [4::Double,5,6] -- (9)
В данном примере мы создаём функцию-обёртку tester для функции tester', имеющей тип:
tester' :: String -> [String] -> IO ()
Пройдёмся по тексту:
они описываю как можно конвертировать значения заданного типа (Integer, () и т.д.), в значения типа элементов списка параметров (String). Тип задаётся либо именем ((5), (6)) либо выражением ((7), (8)). Обратите внимание, что сами элементы передаются тоже как переменные параметры!
Идём дальше, точнее возвращаемся к примеру с обратной польской нотацией [7]:
{-# LANGUAGE TemplateHaskell, FlexibleInstances, ExtendedDefaultRules, GADTs #-} --
import Data.Function.Vargs
data Expr = Num Double | Op (Double -> Double -> Double)
calcRPN' :: [Expr] -> Double
calcRPN' = head . foldr rpnStep [] . reverse
rpnStep :: Expr -> [Double] -> [Double]
rpnStep (Num n) stack = n : stack
rpnStep (Op f) (x:y:stack) = (f x y) : stack
$( return [] )
defVargsFun "calcRPN" ['calcRPN']
(''Integer, [| Num . fromIntegral |])
(''String, [| Num . fst . head . (reads :: ReadS Double) |])
(Genz [t| Double -> Double -> Double |], [| Op |]) -- (1)
([t| [Double] |], [| Num . sum |])
main = do
print $ calcRPN' [Num 5, Num 5, Op (*)]
print $ calcRPN [1::Double,2,3] "5" (+) 7 (*)
В этом примере всё аналогично предыдущему, за исключением одного интересного момента (1): тут мы используем не просто TypeQ, а некоторую обёртку Genz над ним. Эта обёртка заставляет генератор строить экземпляр вида:
instance a ~ Double => ArgSrc (a -> a -> a) where
вместо стандартного
instance ArgSrc (Double -> Double -> Double) where
который в данном случае не пройдёт проверку типов.
Ну и последний пример, та самая функция printf, точнее ей схематичный аналог:
{-# LANGUAGE TemplateHaskell, FlexibleInstances, ExtendedDefaultRules, ExistentialQuantification #-}
import Data.Function.Vargs
type FmtRes = (String, String)
class PfVal a where
doFmt :: FmtRes -> a -> FmtRes
instance PfVal Integer where
doFmt (fmt, res) x =
let (b, s) = span (/= '%') fmt
in (res ++ (tail . tail $ s), b ++ show x)
instance PfVal Double where
doFmt (fmt, res) x =
let (b, s) = span (/= '%') fmt
in (res ++ (tail . tail $ s), b ++ show x)
instance PfVal String where
doFmt (fmt, res) x =
let (b, s) = span (/= '%') fmt
in (res ++ (tail . tail $ s), b ++ x)
data PfValWrap = forall a. PfVal a => Val a -- (1)
printf_String :: String -> [PfValWrap] -> String -- (2)
printf_String fmt vs =
uncurry (flip (++)) $ foldl step (fmt, "") vs
where step fmt (Val f) = doFmt fmt f
printf_IO :: String -> [PfValWrap] -> IO () -- (3)
printf_IO fmt = putStrLn . printf_String fmt
$( return [] )
defVargsFun "printf"
['printf_String, 'printf_IO] -- (4)
[''Integer, ''Double, ''String]
main :: IO ()
main = do
let fmt = "Number one is %d, number two is %f and string is "%s""
printf_IO fmt [Val 100, Val 123.456, Val "ok"]
putStrLn $ printf fmt 100 123.456 "ok"
printf fmt 100 123.456 "ok"
Тут стоит отметить три новых момента:
Теперь пару слов о том, как всё это устроено. Собственно всё что делает defVargsFun, это создаёт несколько классов и экземпляров, на основании информации полученной от reify [9], а также декларацию и определение самой функции с переменным числом параметров. Вся эта «кухня» соответствует общей схеме, ранее рассмотренной на примерах. Опять же нагляднее и проще будет продемонстрировать на примере, что именно генерируется. Рассмотрим код, генерируемый вызовом:
defVargsFun "printf"
['printf_String, 'printf_IO]
[''Integer, ''Double, ''String]
Этот код можно посмотреть если запустить ghc с ключом -ddump-splices. Для наглядности, я поправил форматирование и убрал лишние скобки:
class ArgPrc_printf_aa3M a where -- (1)
prc_printf_aa3O :: String -> [PfValWrap] -> a -- (2)
class ArgSrc_printf_aa3N a where -- (3)
toArg_printf_aa3Q :: a -> PfValWrap -- (4)
instance ArgPrc_printf_aa3M String where -- (5)
prc_printf_aa3O a1 = printf_String a1 . reverse
instance ArgPrc_printf_aa3M (IO ()) where -- (6)
prc_printf_aa3O a1 = printf_IO a1 . reverse
-- (7)
instance (ArgSrc_printf_aa3N a, ArgPrc_printf_aa3M r) => ArgPrc_printf_aa3M (a -> r) where
prc_printf_aa3O a1 acc_printf_aa3P
= prc_printf_aa3O a1 . (: acc_printf_aa3P) . toArg_printf_aa3Q
-- (8)
instance ArgSrc_printf_aa3N PfValWrap where
toArg_printf_aa3Q = id
instance ArgSrc_printf_aa3N Integer where
toArg_printf_aa3Q = Val
instance ArgSrc_printf_aa3N Double where
toArg_printf_aa3Q = Val
instance ArgSrc_printf_aa3N String where
toArg_printf_aa3Q = Val
-- (9)
printf :: forall a. ArgPrc_printf_aa3M a => String -> a
printf a1 = prc_printf_aa3O a1 []
Монада Q обеспечивает нам генерацию уникальных имён — отсюда «заковыристые» окончания в названиях. Пройдёмся по тексту:
Исходный код модуля Data.Function.Vargs с комментариями, а также вышеприведённые примеры его использования лежат тут [11], документация в формате haddoc [12] доступна здесь [13]и в составе пакета. В настоящий момент пакет находится в стадии experimental от слова «совсем» ;)
Возможно со временем доведу до ума — как минимум надо сделать анализ и обработку ошибочных ситуаций (недопустимые или несовместимые типы), как максимум:
Тогда, думаю, не стыдно будет выложить на hackage [15] (хотя там уже есть достойные пакеты типа HList [16] на похожие темы).
Полезные ссылки по теме:
Автор: Wardopdem
Источник [19]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/haskell/250188
Ссылки в тексте:
[1] каррирование: https://ru.wikipedia.org/wiki/Каррирование
[2] printf: http://hackage.haskell.org/package/base-4.9.1.0/docs/src/Text.Printf.html#printf
[3] wiki.haskell: https://wiki.haskell.org/Varargs
[4] ФП: https://ru.wikipedia.org/wiki/Функциональное_программирование
[5] Template Haskell: https://wiki.haskell.org/Template_Haskell
[6] обратной польской нотации: https://ru.wikipedia.org/wiki/Обратная_польская_запись
[7] обратной польской нотацией: #RPN
[8] printf: #printf
[9] reify: http://hackage.haskell.org/package/template-haskell-2.11.1.0/docs/Language-Haskell-TH-Syntax.html#v:reify
[10] здесь: https://ghc.haskell.org/trac/ghc/ticket/9813
[11] тут: https://github.com/wardopdem/vargs
[12] haddoc: https://www.haskell.org/haddock/
[13] здесь : https://wardopdem.github.io/vargs/Data-Function-Vargs.html
[14] альтернативные: http://okmij.org/ftp/Haskell/polyvariadic.html#polyvar-fn
[15] hackage: http://hackage.haskell.org/
[16] HList: http://hackage.haskell.org/package/HList
[17] Polyvariadic functions: https://wiki.haskell.org/Polyvariadic_functions
[18] Existential type: https://wiki.haskell.org/Existential_type
[19] Источник: https://habrahabr.ru/post/324190/
Нажмите здесь для печати.