Как использовать монаду Supply для создания функции, генерирующей глобально уникальные имена?

Задний план:

Я делаю проект перевода кода, который требует от меня создания имен переменных. Ни одно из имен, которые я генерирую, не должно дублировать друг друга.

Я действительно расстроен, так как это было бы глупо просто и элегантно с функцией генератора Python.

Что я пробовал:

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

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

За короткое время работы с Haskell я так и не освоился с монадами, но у меня было подозрение, что я могу использовать оболочку для монады State для имитации глобальной переменной-счетчика. После 3 дней безделья, пытаясь найти монады и создать свою собственную, а затем пытаясь изменить чужие монады, чтобы сгенерировать нужные мне значения, я, наконец, смирился с прямым использованием чужой высокоуровневой монады (возможно, с небольшими изменениями.)

Моя проблема сейчас:

Я определил MonadSupply и MonadUnique в виде пары модулей, которые, вероятно, обеспечивают простой интерфейс, который мне нужен. К сожалению, я не могу понять, как их использовать.

В частности, в документации по модулю MonadSupply есть хороший пример использования:

runSupplyVars x = runSupply x vars
    where vars = [replicate k ['a'..'z'] | k <- [1..]] >>= sequence

Похоже на то, что я хочу! Как только я получил модуль для компиляции, я проверил тип этой функции в интерпретаторе:

> :t runSupplyVars
runSupplyVars :: Supply [Char] a -> Identity (a, [[Char]])

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

Вопросы:

Может ли кто-нибудь привести пример использования этой функции runSupplyVars?

Можно ли сделать с ним то, о чем я думаю? Я хочу иметь функцию, которую я могу вызывать из любого места в программе, которая будет предоставлять мне другое имя переменной или целое число при каждом вызове.


functional-programming unique haskell monads state-monad
person machine yearning    schedule 03.04.2014    source источник

Ответы (1)


arrow_upward
6
arrow_downward

Чтобы на самом деле использовать монаду Supply, вы должны структурировать свой код с помощью do нотации и вызвать функцию supply когда вам действительно нужно имя.

Например, это создаст новое имя переменной с префиксом var_, просто чтобы показать, как вы можете получить что-то из поставки и использовать это:

newVar :: Supply [Char] [Char]
newVar = do
    name <- supply
    return ("var"_++name)

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

Наконец, вам понадобится runIdentity из Control.Monad.Identity, чтобы распаковать результат runSupplyVars в базовый кортеж типа (a, [[Char]]), а затем отбросить второе значение, которое представляет собой (бесконечный) список неиспользуемых имен. Возможно, вам лучше переопределить runSupplyVars, чтобы сделать это за вас:

import Control.Monad.Identity

[...]

runSupplyVars :: Supply [Char] a -> a
runSupplyVars x = fst (runIdentity (runSupply x vars))
    where vars = [replicate k ['a'..'z'] | k <- [1..]] >>= sequence

Вот более полный пример, объединяющий все это. Обратите внимание на различные монады, с которыми используется нотация do — IO для функции main и Supply [Char] для realProgram и, вероятно, большая часть остального кода в увеличенной версии:

import MonadSupply
import Control.Monad.Identity

main :: IO ()
main = do
    let result = runSupplyVars realProgram
    print result

realProgram :: Supply [Char] Int
realProgram = do
    x <- newVar
    return 0

newVar :: Supply [Char] [Char]
newVar = do
    name <- supply
    return ("var_"++name)

runSupplyVars :: Supply [Char] a -> a
runSupplyVars x = fst (runIdentity (runSupply x vars))
    where vars = [replicate k ['a'..'z'] | k <- [1..]] >>= sequence
person GS - Apologise to Monica    schedule 03.04.2014
comment
Думаю, моя самая большая проблема связана с нотацией do. Если я вызываю runSupplyVars из первой строки моего блока do, например p <- runSupplyVars, то кажется, что каждая вторая строка в блоке должна иметь тип Supply [Char] t0 -> b0 (согласно моим сообщениям об ошибках компиляции). Я предполагаю, что это означает, что любая функция верхнего уровня, которую я использую для запуска моего перевода (скажем, foo), нуждается в этом возвращаемом типе, тогда я могу свободно вызывать newVar в foo и любую функцию, которую я вызываю в foo. Могу ли я просто вернуть какой-то мусор такого типа? - person machine yearning; 04.04.2014
comment
Хорошо, я вижу часть вашей проблемы - нотация do для функции main, которая является точкой входа из внешнего мира, работает с монадой IO, тогда как остальная часть вашего кода будет работать с монадой Supply. Я добавил пример этого. - person GS - Apologise to Monica; 04.04.2014
comment
Кстати, если вы также хотите использовать IO в остальной части вашего кода, вам понадобится либо монадный преобразователь (SupplyT на вики-странице), либо вместо этого используйте IORef для передачи имени. Это добавляет еще один слой для понимания, поэтому, вероятно, лучше сначала разобраться с этим стилем. - person GS - Apologise to Monica; 04.04.2014
comment
Я думаю, вы могли неправильно прочитать, это t0, а не IO. Я не выполняю ввод-вывод и не использую эту монаду (если только вы не говорите, что мне это нужно?). Я внимательно рассмотрю ваш новый пример кода. Кстати, если я это выясню, ты заработаешь солидную награду. - person machine yearning; 04.04.2014
comment
Я правильно понял t0 — я догадался, что вы используете IO из-за того, что вы сказали о вызове runSupplyVars из первой строки моего do, из чего я сделал вывод, что это вполне может быть из main, который находится в IO монаде. Монада Supply работает следующим образом: вы создаете большую операцию типа Supply [Char] a, а затем избавляетесь от нее в чистом коде, используя runSupplyVars. Поэтому независимо от того, откуда вы его вызываете, вызов будет больше похож на let result = runSupplyVars realProgram, чем на do p <- runSupplyVars. - person GS - Apologise to Monica; 04.04.2014
comment
Так много блоков do и странных типов, что это кажется таким же беспорядочным, как мой исходный код. Я просто возвращаюсь к передаче аккумуляторов, по крайней мере, я понял, как это работает. - person machine yearning; 04.04.2014
comment
Достаточно справедливо - использование монад сопряжено с накладными расходами, но они действительно проявляются в более сложных сценариях, где они могут скрывать гораздо больше шаблонов, чем одна переменная состояния. Использование одного здесь также несколько усложняет испорченное и случайное повторное использование одного и того же имени переменной. - person GS - Apologise to Monica; 04.04.2014