Function: Inside

[nsk.coder]

Function: Inside

Добрый день всем!

Разрабатывая одну задачку, вышел на следующий ряд проблем, которые не знаю как решить в Haskell, может быть, кто-то знает или подскажет?

1. Можно ли задать функцию высшего порядка (т.е., принимающую на вход какую-либо другую функцию), которая может определить тип переданной в аргументе функции и выдать его, скажем в виде строки?  (скажем, как это делает команда :t  в ghci)  Мне кажется, что я где-то встречал упоминание об этой (или похожей)  возможности штатными средствами, возможно даже в Haskell-98 Report.

2. Другой вариант этой же проблемы (мне как раз он и нужен): можно ли определить число аргументов (арность) переданной в аргументе функции? Например, для (+)  будет два, для snd будет один.

3. Можно ли для произвольно переданного кортежа определить его размерность?

4. Можно ли задать функцию, которая будет задана только от (целых, положительных) нумералов (литералов?)? Т.е. ее аргументами могут быть только числа из Integer, а более сложные выражения, такие как например (2*3-4) уже не могут. Ведь для всех числовых функций, например того же сложения (+) аргументы могут быть не только числа, но и любые сложные выражения (термы), возвращающие числа в качестве результата.

Я понимаю, что на первый взгляд вопросы 1-3 сразу спотыкаются об статическую проверку типов. Ведь мы не можем передать в качестве аргумента “абстрактную” функцию, у которой не описан жестко заранее ее тип. Но тогда, может быть, как-то можно эти вопросы расширить/сузить, чтобы какое-то решение нашлось. Например, по п.1 можно не ограничивать задачу функциями и тогда видно, что решение есть, раз команда :t работает в ghci и умеет распознавать тип.

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

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

Возможно есть что более-менее “инсайдерское”, что позволяет из “глубин” Haskell вытащить информацию о переданных функциях? Ведь компилирующая/исполняющая система того же ghc этой информацией и обладает и пользуется, я так думаю.

[Dmytro Starosud]

Доброго времени суток!

О втором: посмотрите как используются классы для функций переменного количества аргументов (как PrintF).

С уважением,
Дмитрий

11 марта 2013 г., 22:00 пользователь nsk.coder <nsk....@gmail.com> написал:

--
--
Отправить сообщение в SPb HUG: spb...@googlegroups.com
Отменить подписку: spbhug-un...@googlegroups.com
Страница группы: http://groups.google.com/group/spbhug?hl=ru
---
Вы получили это сообщение, поскольку подписаны на группу SPb Haskell User Group.
 
Чтобы отказаться от подписки на эту группу и перестать получать из нее сообщения, отправьте электронное письмо на адрес spbhug+un...@googlegroups.com.
Подробнее о функциях можно узнать на странице https://groups.google.com/groups/opt_out.
 
 

[Alexander V Vershilov]

Здравствуйте

> import Data.Typeable

> {- 1. Можно ли задать функцию высшего порядка

> (т.е., принимающую на вход какую-либо другую функцию),
> которая может определить тип переданной в аргументе функции
> и выдать его, скажем в виде строки? (скажем, как это делает
> команда :t в ghci) Мне кажется, что я где-то встречал
> упоминание об этой (или похожей) возможности

> штатными средствами, возможно даже в Haskell-98 Report. -}

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

> q1_0 :: (Typeable a, Typeable b) => (a -> b) -> String
> q1_0 = show . typeOf

*Main> q1_0 (+)
"Integer -> Integer -> Integer"

Или поскольку в хацкеле всё является фунцией, то

> q1_1 :: Typeable a => a -> String
> q1_1 = show . typeOf

но выполнить следующий код нельзя, в общем случае нельзя
если Typeable тип snd не выводится

*Main> q1_1 (snd)

<interactive>:12:1:
No instance for (Typeable b0) arising from a use of `q1_1'

> {-

> 2. Другой вариант этой же проблемы (мне как раз он и нужен):
> можно ли определить число аргументов (арность) переданной в

> аргументе функции? Например, для (+) будет два, для snd будет один. -}

Если честно, то правильный ответ здесь будет

> arity = const 1

Но если не занудствовать, то здесь можно пойти тем же путем:

> q2_0 :: Typeable a => a -> Int
> q2_0 = length . typeRepArgs . typeOf

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

Поскольку можно ограничиться только Bool, то можно написать следующее

> class BArity b where
> barity :: b -> Int
> instance BArity Bool where
> barity _ = 0
> instance (BArity x) => BArity (b -> x) where
> barity f = 1 + barity (f undefined)

Расширив класс и для других случаев, которые надо поддерживать.

> -- 3. Можно ли для произвольно переданного кортежа определить его размерность?

Зачем? Можно с помощью TemplateHaskell, например.

> {- 4. Можно ли задать функцию, которая будет задана только от (целых, положительных)

> нумералов (литералов?)?
> Т.е. ее аргументами могут быть только числа из Integer, а более сложные выражения,
> такие как например (2*3-4) уже не могут. Ведь для всех числовых функций,
> например того же сложения (+) аргументы могут быть не только числа, но и
> любые сложные выражения (термы), возвращающие числа в качестве результата.

Отвечая на вопрос про нумералы, зачем? Т.е. должно быть нельзя написать:
foo (2*3-4), а можно ли let t=2*3-4 in foo t, или let !t=2*3-4 in foo t,
в этом случае t будет вычислено до того, как будет передано в foo.

--
Alexander

[Roman Cheplyaka]

Похоже на http://meta.stackoverflow.com/q/66377

* nsk.coder <nsk....@gmail.com> [2013-03-11 13:00:32-0700]
> *

>
> Function: Inside
>
> Добрый день всем!
>
> Разрабатывая одну задачку, вышел на следующий ряд проблем, которые не знаю
> как решить в Haskell, может быть, кто-то знает или подскажет?
>
> 1. Можно ли задать функцию высшего порядка (т.е., принимающую на вход
> какую-либо другую функцию), которая может определить тип переданной в
> аргументе функции и выдать его, скажем в виде строки? (скажем, как это
> делает команда :t в ghci) Мне кажется, что я где-то встречал упоминание
> об этой (или похожей) возможности штатными средствами, возможно даже в
> Haskell-98 Report.
>
> 2. Другой вариант этой же проблемы (мне как раз он и нужен): можно ли
> определить число аргументов (арность) переданной в аргументе функции?
> Например, для (+) будет два, для snd будет один.
>
> 3. Можно ли для произвольно переданного кортежа определить его размерность?
>
> 4. Можно ли задать функцию, которая будет задана только от (целых,

> положительных) нумералов *(литералов?)*? Т.е. ее аргументами могут быть

> *

[Maxim Taldykin]

По поводу 2 был когда-то вопрос на SO:
http://stackoverflow.com/questions/8369114/haskell-function-to-determine-the-arity-of-functions
И соглашусь с Романом: судя по вопросам вы свою "одну задачку", скорее
всего, не с той стороны решаете.

Можете пояснить, что значит пункт 4? Хотите запретить писать выражения
f (2+3)? А зачем?

12 марта 2013 г., 0:00 пользователь nsk.coder <nsk....@gmail.com> написал:

[nsk.coder]

Коллеги, большое вам спасибо за советы!

В общем-то, я увидел направление где искать.
--------------------------------------
Немного более подробно:

Dmytro Starosud:

>О втором: посмотрите как используются классы для функций переменного
>количества аргументов (как

>PrintF<http://rosettacode.org/wiki/Variadic_function#Haskell>

Maxim Taldykin:

>По поводу 2 был когда-то вопрос на SO:

>http://stackoverflow.com/questions/8369114/haskell-function-to-determ...

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

А 1-я проблема кажется самой интересной -- мне очень хотелось бы
понять как GHCI реализует команду :t хотя бы в общих чертах.

--------------------------------------

Alexander V Vershilov:

> Если честно, то правильный ответ здесь будет
> arity = const

Я может быть Вас на понял, но именно это не работает:

Ваше arity (+) дает 1, вообще всегда 1.

Но рассмотреть Data.Typeable похоже, обязательно!

--------------------------------------

Александр, а чем же вывод типов в ghci отличается от вывода типов в
ghc? И что мешает получить сведения о типах юзеру при компиляции?

[nsk.coder]

Роман, я правильно понял, что эта ссылка является в некотором смысле завуалированной оценкой состоятельности автора и описываемых им задач, вместо конкретных предложений?

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

Теперь о самих задачах(проблемах). Разумеется, у некоторых из этих проблем есть корни -- и для одной из них (#2) я даже описал, откуда и для чего она мне была нужна на практике. Некоторые возникли по ассоциации и интересны как "странные" задачки.

Но в данном контексте -- это просто проблемы и просто вопрос, можно ли их решить на Haskell?

Представьте себе, что еще не создан GHCI, а есть только GHC -- и какой-то разработчик GHCI, желающий реализовать фичу :t, спрашивает об этом на haskell-форуме, мол можно ли это сделать на Haskell. А ему говорят -- а зачем это? В haskell и так все есть для работы с типами и т.д. Да может быть разработчик сам не понимает чего он хочет? Смешно?!

Вот и мне интересно, как например, эта команда :t реализована...

вторник, 12 марта 2013 г., 22:46:53 UTC+7 пользователь Roman Cheplyaka написал:

Похоже на http://meta.stackoverflow.com/q/66377

[Alexander V Vershilov]

Здравствуйте.

> Alexander V Vershilov:
>> Если честно, то правильный ответ здесь будет
>> arity = const
>
> Я может быть Вас на понял, но именно это не работает:
>
> Ваше arity (+) дает 1, вообще всегда 1.

Да, это была отсылка к тому факту, что все функции в haskell имеют арность 1,
а функция с типом (a -> b -> c), является функцией a -> (b -> c),
понимание этого
может быть весьма полезно, например построение таблиц истиности как,
использует этот факт (возможно есть более хорошие имплементации):

> class BArity b where
> btable :: b -> [([Bool],Bool)]
> instance BArity Bool where
> btable x = [([],x)]
> instance (BArity x) => BArity (Bool -> x) where
> btable f = map (first (True:)) (btable $ f True) ++
> map (first (False:)) (btable $ f False)

btable (&&)
[([True,True],True),([True,False],False),([False,True],False),([False,False],False)]

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

> Но рассмотреть Data.Typeable похоже, обязательно!
>
> --------------------------------------
>
> Александр, а чем же вывод типов в ghci отличается от вывода типов в
> ghc? И что мешает получить сведения о типах юзеру при компиляции?

Ничем, но при этом в итоговой программе собранной ghc стирается информация
о типах, в отличи от этого ghci может "не выводить" типы до конца, а делать
это только в случае необходимости, в этом основное отличие, т.к. в ghci может
существовать тип "a", а при сборке ghc он должен быть выведен в конкретный тип.

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

--
Alexander

[Roman Cheplyaka]

* nsk.coder <nsk....@gmail.com> [2013-03-12 23:18:07-0700]

> Роман, я правильно понял, что эта ссылка является в некотором смысле
> завуалированной оценкой состоятельности автора и описываемых им задач,
> вместо конкретных предложений?

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

> Теперь о самих задачах(проблемах). Разумеется, у некоторых из этих проблем
> есть корни -- и для одной из них (#2) я даже описал, откуда и для чего она
> мне была нужна на практике.

Правильно. И обратите внимание:

1. Как только вы сказали, какую проблему решаете, вам Дмитрий сразу
указал на ее решение.
2. Решение это не предполагает "подсчет аргументов".
3. Если бы вам показали, как подсчитывать аргументы, проблему бы это не
решило, а привело бы вас к следующему вопросу, например "как
применить функцию от n аргументов к n аргументам".

Так что это отлично иллюстрирует мой тезис.

> Представьте себе, что еще не создан GHCI, а есть только GHC -- и какой-то

> разработчик GHCI, желающий реализовать фичу *:t*, спрашивает об этом на

> haskell-форуме, мол можно ли это сделать на Haskell. А ему говорят -- а
> зачем это? В haskell и так все есть для работы с типами и т.д. Да может
> быть разработчик сам не понимает чего он хочет? Смешно?!
>

> Вот и мне интересно, как например, эта команда *:t* реализована...

Команда :t реализована в интерпретаторе языка, а не в самом языке.
Задача, которую эта команда решает, — это

Имея текст программы на Haskell и имя функции в этой программе,
вывести тип этой функции.

а не

Получив на вход аргумент, вывести его тип.

Чтобы разница была более очевидной, представьте себе, что ghci написан
на C.

Роман

[Roman Cheplyaka]

* Alexander V Vershilov <alexander...@gmail.com> [2013-03-13 11:59:24+0400]

> Ничем, но при этом в итоговой программе собранной ghc стирается информация
> о типах, в отличи от этого ghci может "не выводить" типы до конца, а делать
> это только в случае необходимости, в этом основное отличие, т.к. в ghci может
> существовать тип "a", а при сборке ghc он должен быть выведен в конкретный тип.

Интересное утверждение. Можно пример?

Роман

[Alexander V Vershilov]

2013/3/13 Roman Cheplyaka <ro...@ro-che.info>:

Это моё упрощенное понимание ситуации, которое иллюстрирует разницу,
и может не точно описывать, реальный процесс работы. Имеется ввиду, что
фунция snd в ghci существует вне контекста, и мы вправе считать, что её тип
snd :: (a, b) -> b, подставив вместо реального типа некий абстрактный тип, и
выводя его пользователю если он запрашивает. В отличии от этого при сборке ghc
нам необходимо вывести все конкретные типы, т.к. они фиксируются контекстом.
Хотя пример main = print $ snd (1,undefined)) играет против меня, но насколько
я понимаю в этом случае сборка происходит или за счет оптимизатора,
или приведения к типам по умолчанию.

Или нужно привести пример к другой части утверждения.

--
Alexander

[Alexander V Vershilov]

2013/3/13 Alexander V Vershilov <alexander...@gmail.com>:

UPD. Посмотрел core приведенного мной антипримера и документацию про
GHC.Prim.Any
и понял, что все же стоит добавить, что и в случае с ghc возможны
варианты сделать тип
невыведенным к конкретных местах программы. Воспользовавшить, например,
квалификатором forall. Поэтому мое утверждение должно звучать, что
типы должны быть
выведены в том, случае, если они не используются в контексте, где
допустимо "обобщение".
GHCi же в этом смысле является функцией, позволяющей обобщения (forall), поэтому

Прошу прощения за сумбурность изложения.

--
Alexander

[Roman Cheplyaka]

* Alexander V Vershilov <alexander...@gmail.com> [2013-03-13 12:24:42+0400]

Я понял, что вы имеете в виду, но, боюсь, ваше понимание ошибочно.

Красота параметрического полиморфизма как раз заключается в том, что
операционная семантика полиморфных функции не зависит от типов. Все типы
можно "стереть" во время выполнения. Следовательно, чтобы такую функцию
скомпилировать, "фиксировать" типы нет никакой необходимости. Ей эти
типы просто не интересны.

Дабы не было подозрения в том, что работает оптимизатор или
подставляются дефолтные типы, напишите свою собственную функцию snd и
скомпилируйте ее отдельно:

% cat snd.hs
module Snd where

mysnd :: (a,b) -> b
mysnd (x,y) = y

% ghc snd.hs
[1 of 1] Compiling Snd ( snd.hs, snd.o )

Давайте заглянем в интерфейсный файл:

% ghc --show-iface snd.hi
Magic: Wanted 129742,
got 129742
Version: Wanted [7, 0, 6, 1, 2, 0, 1, 2, 1, 2, 0, 7],
got [7, 0, 6, 1, 2, 0, 1, 2, 1, 2, 0, 7]
Way: Wanted [],
got []
interface main:Snd 706120121207
interface hash: 10be1e29d8288d9ccdf05af1884733a7
ABI hash: 038c33988773e5deb4d3ee9eb10b2c59
export-list hash: a7bc02fe1c8a7b361f9b9c5744fca487
orphan hash: 693e9af84d3dfcc71e640e005bdc5e2e
flag hash: 1e8135cb44ef6dd330f1f56943d1f463
used TH splices: False
where
exports:
Snd.mysnd
module dependencies:
package dependencies: base* ghc-prim integer-gmp
orphans: base:GHC.Base base:GHC.Float base:GHC.Real
family instance modules:
import -/ base:Prelude d8be97e18e069691fc159d89de212792
9b4ad8638158fdbde051adfba489ffd7
mysnd :: forall a b. (a, b) -> b
vectorised variables:
vectorised tycons:
vectorised reused tycons:
scalar variables:
scalar tycons:
trusted: safe-inferred
require own pkg trusted: False

Здесь надо обратить внимание вот на что:

* функция snd действительно скомпилирована с полиморфным типом (мы ведь
не знаем, на каких типах она будет использоваться) — и интерфейсный
файл это подтверждает;
* но в интерфейсном файле нет ее определения (т.к. я компилировал без
-O), поэтому у оптимизатора нет шансов ее заинлайнить и как-то упростить.

Во время исполнения пара (tuple) представлена как struct с двумя полями —
указателями на первый и второй элемент. (Аналогично представляется
любой другой data constructor.) Чтобы взять второе поле этой структуры
вовсе не обязательно знать, что именно скрывается за указателем.

Роман

[Alexander V Vershilov]

2013/3/13 Roman Cheplyaka <ro...@ro-che.info>:
> * Alexander V Vershilov <alexander...@gmail.com> [2013-03-13 12:24:42+0400]
>> 2013/3/13 Roman Cheplyaka <ro...@ro-che.info>:
>> > * Alexander V Vershilov <alexander...@gmail.com> [2013-03-13 11:59:24+0400]
>> >> Ничем, но при этом в итоговой программе собранной ghc стирается информация
>> >> о типах, в отличи от этого ghci может "не выводить" типы до конца, а делать
>> >> это только в случае необходимости, в этом основное отличие, т.к. в ghci может
>> >> существовать тип "a", а при сборке ghc он должен быть выведен в конкретный тип.
>> >
>> > Интересное утверждение. Можно пример?
>> >
>> > Роман
>> >
>>
>> Это моё упрощенное понимание ситуации, которое иллюстрирует разницу,
>> и может не точно описывать, реальный процесс работы. Имеется ввиду, что
>> фунция snd в ghci существует вне контекста, и мы вправе считать, что её тип
>> snd :: (a, b) -> b, подставив вместо реального типа некий абстрактный тип, и
>> выводя его пользователю если он запрашивает. В отличии от этого при сборке ghc
>> нам необходимо вывести все конкретные типы, т.к. они фиксируются контекстом.
>> Хотя пример main = print $ snd (1,undefined)) играет против меня, но насколько
>> я понимаю в этом случае сборка происходит или за счет оптимизатора,
>> или приведения к типам по умолчанию.

> Я понял, что вы имеете в виду, но, боюсь, ваше понимание ошибочно.

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

> Красота параметрического полиморфизма как раз заключается в том, что
> операционная семантика полиморфных функции не зависит от типов. Все типы
> можно "стереть" во время выполнения.

Именно на этом строилось моё утверждение, что код собранный ghc не будет
иметь доступа к типам и они будут стерты.

> не знаем, на каких типах она будет использоваться) -- и интерфейсный

> файл это подтверждает;
> * но в интерфейсном файле нет ее определения (т.к. я компилировал без
> -O), поэтому у оптимизатора нет шансов ее заинлайнить и как-то упростить.
>

> Во время исполнения пара (tuple) представлена как struct с двумя полями --

> указателями на первый и второй элемент. (Аналогично представляется
> любой другой data constructor.) Чтобы взять второе поле этой структуры
> вовсе не обязательно знать, что именно скрывается за указателем.
>
> Роман

Похоже проблема в моем утверждении заключалась в том, что при описании
своего понимания я рассматривал уже собранную программу, а не модуль.
Да, у функций возможен полиморфизм вида (forall a), но будучи подставленной
в контекст эти типы должны быть выведены (собственно это необходимое условие,
для того, чтобы они могли быть стерты). Естественно, в случае, если поле не
используется совсем (мой пример), то оно выводится в тип GHC.Prim.Any. Так в
ghci все функции у нас остаются полиморфными, поскольку они

--
Alexander

[Roman Cheplyaka]

* Alexander V Vershilov <alexander...@gmail.com> [2013-03-13 13:27:21+0400]

> Похоже проблема в моем утверждении заключалась в том, что при описании
> своего понимания я рассматривал уже собранную программу, а не модуль.
> Да, у функций возможен полиморфизм вида (forall a), но будучи подставленной
> в контекст эти типы должны быть выведены (собственно это необходимое условие,
> для того, чтобы они могли быть стерты). Естественно, в случае, если поле не
> используется совсем (мой пример), то оно выводится в тип GHC.Prim.Any.

Если, как в вашем примере, тип не используется, то его можно
инстанциировать любым типом. То, что GHC использует конкретно Any (а не
() или Bool) — деталь реализации.

Но, раз вы упомянули про Any, возможно вы имели в виду что-то вроде

Prelude> x <- return undefined
Prelude> :t x
x :: GHC.Prim.Any *

Это действительно артефакт ghci.

> Так в ghci все функции у нас остаются полиморфными, поскольку они

У вас части письма куда-то пропадают.

Роман