Как значения анализируются для этой функции вставки в haskell - PullRequest
Новая
       12

Как значения анализируются для этой функции вставки в haskell

0 голосов
/ 15 июня 2019

Я пытаюсь выяснить этот кусок кода, как он на самом деле работает.Эта функция реализует концепцию Set в Haskell.

У меня есть общее представление о множестве в Haskell, что оно похоже на функцию (типа IntSet = a -> Bool), но я не совсем понимаю цель использования этого, я имею в виду, что это похоже на другоеПростая функция и логика, стоящие за вставкой: если вы хотите вставить элемент в набор, вы просто расширяете характеристическую функцию, чтобы включить регистр для этого.

Здесь я пытаюсь понять эту функцию вставки, как разобрать значения, чтобы вставить функцию, а также вставить элемент в нее.

type IntSet = Int -> Bool

Если у нас есть пустой набор, если мы хотим вставить в него значения, он всегда будет возвращать False, потому что он не содержит значения, Understandable!но как вставить значение и увидеть его на самом деле вставлен.

empty :: IntSet 
empty = \ _ -> False 

insert :: Int -> IntSet -> IntSet 
insert x s = \y -> x ==y then True else s y 


input : insert 2 empty 0



result = False

Как анализируются значения для вставки функции и каковы значения s x и y и в другом случае, когда он возвращает s y, как это обрабатывается.

Я только начинающий, любой ценный вклад будет оценен.

1 Ответ

2 голосов
/ 15 июня 2019

Представляет набор как функцию, которая, учитывая Int, сообщает вам, находится ли он в et (возвращая True) или нет (возвращая False).

Таким образом, пустой набор - это функция, которая возвращает False независимо от того, какой аргумент вы указали.

Вставка в набор означает возврат нового набора / функции на основе старого набора / функции.

В вашем определении функции есть небольшая опечатка, так как отсутствует ключевое слово if: 

insert :: Int -> IntSet -> IntSet
insert x s = \y -> if x == y then True else s y

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

let newset = insert 3 empty in newset 3

оценивается как True, потому что 

newset 3 == (insert 3 empty) 3
         == (\y -> if 3 == y then True else empty 3) 3
         == if 3 == 3 then True else empty 3
         == True

, в то время как let newset = insert 3 empty in newset 4 возвращает False, потому что 

newset 4 == (insert 3 empty) 4
         == (\y -> if 3 == y then True else empty 3) 4
         == if 4 == 3 then True else empty 3
         == empty 3
         == (\_ -> False) 3
         == False

Это прекрасно работает (хотя и немного неэффективно) для запроса определенного значения. Но что, если вы просто хотите увидеть все значения, содержащиеся в наборе? Концептуально это легко (поскольку Int конечно, так же как и все возможные наборы): просто отфильтруйте список всех значений Int, используя набор / функцию: 

setToList :: IntSet -> [Int]
setToList s = filter s [minBound..maxBound]

Учитывая что-то вроде setToList (insert 3 (insert 5 empty)), просто (хотя и утомительно) показать, что

  • (insert 3 (insert 5 empty)) minBound Неверно,
  • (insert 3 (insert 5 empty)) (minBound + 1) Неверно,
  • ...
  • (insert 3 (insert 5 empty)) 0 Неверно,
  • (insert 3 (insert 5 empty)) 1 Неверно,
  • (insert 3 (insert 5 empty)) 2 Неверно,
  • (insert 3 (insert 5 empty)) 3 верно,

  • и т.д.

    так что конечным результатом будет список [3, 5]. Однако это занимает некоторое время, поскольку в зависимости от вашей системы список [minBound..maxBound] может содержать довольно много элементов. (Проверьте значения minBound :: Int и maxBound :: Int, чтобы узнать, сколько их.)

Обратите внимание, что setToList завершается только потому, что Int - конечный тип.

...