2

Сложилась такая ситуация:

  • Есть функция fn :: Bool -> Bool -> Bool -> Bool.

  • Есть список, состоящий из списков возможных значений аргументов функции fn: [[False, False, False], ... , [True, True, True]] (генерируется по количеству аргументов функции)

Я хочу достичь чего-то вроде "starred expression" в Python: fn(*[a,b,...,z]) == fn(a,b,...,z) и делаю как-то так, чтобы получить значения функции для всех "аргументных" списков: map (t $ fn) [[False, False, False], [True, True, True]], где t f [x,y,z] = f x y z.

Проблема в том, что аргументов у fn может быть не три, а больше или меньше. Как, соответственно, и элементов в "аргументных" списках.

Как реализовать функцию t, чтобы та принимала вторым аргументом список с переменным количеством элементов? Заранее спасибо!

Edit:

Я дошел до идеального решения, казалось бы: foldl a (\x -> \y -> \z -> z) [1,2,3], где a = \f -> \x -> f x. Проведём бета-редукцию:

  1. a (\x -> \y -> \z -> z) 1 == (\x -> (\t -> \y -> \z -> z) x) 1 == \y -> \z -> z
  2. a (\y -> \z -> z) 2 == (\x -> (\y -> \z -> z) x) 2 == \z -> z
  3. a (\z -> z) 3 == (\x -> (\z -> z) x) 3 == 3

Но:

    • Occurs check: cannot construct the infinite type: t0 ~ t0 -> t0
      Expected type: (t0 -> t0 -> t0 -> t0) -> t0 -> t0 -> t0 -> t0 -> t0
        Actual type: (t0 -> t0 -> t0 -> t0 -> t0)
                     -> t0 -> t0 -> t0 -> t0 -> t0
    • In the first argument of ‘foldl’, namely ‘a’
      In the second argument of ‘($)’, namely
        ‘foldl a (\ x -> \ y -> \ z -> z) [1, 2, 3]’
      In the second argument of ‘($)’, namely
        ‘show $ foldl a (\ x -> \ y -> \ z -> z) [1, 2, 3]’

ЧЯДНТ?

5
  • Что должно происходить если в списке окажется не три элемента? 21 мар 2020 в 23:06
  • Эти "не три" элемента должны будут встать в fn в качестве аргументов. Допустим, "не три" -- это два. Тогда fn будет Bool -> Bool -> Bool и случайно выбранный "аргументный" список будет [False, True]. И тогда: t fn [False, True] вернёт условное True. 21 мар 2020 в 23:17
  • По сути, в случае, когда элемента два, t -- это uncurry, но для списка. Я хочу выяснить, возможно ли сделать "резиновый" uncurry. 21 мар 2020 в 23:21
  • То есть вы хотите сказать, что у функции t тип первого аргумента должен зависеть от значения второго? (обратите внимание: не от типа второго аргумента, а от его значения) 22 мар 2020 в 0:52
  • Нет, гарантируется, что количество аргументов в функции и количество элементов в списке будут совпадать. 22 мар 2020 в 6:59

1 ответ 1

5

"Резиновый" curry сделать конечно можно. Ваш пример с foldl не работает, потому что результат каждой итерации должен быть одного и того же типа, а у вас типы разные: первая итерация Bool -> Bool -> Bool, вторая Bool -> Bool, третья Bool.

Но в Хаскелле есть механизм, позволяющий создавать функции с переменными типами аргументов. Этот механизм - классы.

class CallWithBoolList f where
    t :: f -> [Bool] -> Bool

Здесь f - это тип функции, которую вы хотите вызвать с аргументами из списка, а t - это ваша искомая функция. Её первый параметр - это функция f, второй параметр - список аргументов, а возвращает она результат вызова f с этими аргументами.

Первый случай - базовый: пустой список аргументов. В этом случае тип функции f вырождается просто в Bool. Ведь функция без аргументов - это просто значение. Запишем:

instance CallWithBoolList Bool where
    t b [] = b
    t _ _ = error "Слишком много аргументов"

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

Второй случай - рекурсивный: список аргументов, состоящий из головы и хвоста. В этом случае тип функции f должен быть Bool -> a, где Bool - это её первый аргумент, а a - это "остаток" функции, то есть функция, которая ожидает все аргументы кроме первого, и потом возвращает значение. Запишем:

instance CallWithBoolList a => CallWithBoolList (Bool -> a) where
    t f (x:xs) = t (f x) xs
    t _ [] = error "недостаточно аргументов"

Здесь функция t передаёт первый аргумент ("голову" списка) в функцию f, та возвращает "остаток функции", и он затем передаётся в "предыдущую" версию функции t вместе с остальными аргументами ("хвостом" списка).

Проверим как это работает:

f1 x = not x
f2 x y = x && y
f3 x y z = x && y && z
f4 x y z w = x && y || z && w

main = do
    print $ t f1 [True] -- выводит False
    print $ t f2 [True, False] -- выводит False
    print $ t f3 [True, False, True] -- выводит False
    print $ t f4 [True, True, False, False] -- выводит True
    print $ t f1 [True, False] -- ошибка: слишком много аргументов

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

class CallWithList f res where
    t' :: f -> [res] -> res

instance CallWithList res res where
    t' res [] = res
    t' _ _ = error "слишком много аргументов"

instance CallWithList f res => CallWithList (res -> f) res where
    t' f (x:xs) = t' (f x) xs
    t' _ [] = error "недостаточно аргументов"

Единственное отличие - это дополнительная переменная res, которая присутствует в классе и реализациях, заменяя тип Bool.


Однако, глядя на ваши комментарии, я сомневаюсь, что это именно то, чего вы искали. В частности, обратите внимание, что в моей реализации, если вызвать функцию t с "неправльным" количеством аргументов, она выдаёт ошибку. Но на мой вопрос в комментариях о том, что должно происходить в таком случае, вы ответили:

Эти "не три" элемента должны будут встать в fn в качестве аргументов. Допустим, "не три" -- это два. Тогда fn будет Bool -> Bool -> Bool

Это непонятно. Например, как должна работать вот такая программа:

main = do
    let f x y z = x && y && z
    print $ t f [True, False]

В моей реализации она выдаст ошибку во время выполнения. А чего ожидаете вы?

Допустим, вы скажете, что такая программа не должна компилироваться. Хорошо, тогда пусть список аргументов вводит пользователь:

main = do
    let f x y z = x && y && z
    args <- read <$> readLine
    print $ t f args

Что тогда? Непонятно.

Если вы уточните, что именно вы ожидаете увидеть, возможно я смогу предложить лучшее решение.

1
  • Нет-нет, ваша реализация с классами -- это именно то, что мне было нужно. Спасибо огромное! Отмечу, что для работы кода t' нужны расширения FlexibleInstances и MultiParamTypeClasses. 22 мар 2020 в 6:50

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.