сделать запись и связать подпись - PullRequest
Новая
       39

сделать запись и связать подпись

0 голосов
/ 14 декабря 2018

Я новичок в Haskell и функциональном программировании, и мне было интересно, почему работает такой пример («вложенный цикл»): 

do
  a <- [1, 2, 3]
  b <- [4, 5, 6]
  return $ a * 10 + b

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

Это мое понимание того, что оно превратилось в нечто подобное 

[1, 2, 3] >>= \a -> 
          ([4, 5, 6] >>= \b -> 
                     return $ b * 10 + a)

Я думаю, что это выражение 

[4, 5, 6] >>= \b -> return $ b * 10 + a

Создает список частично примененных функций 

[[40 + a], [50 + a], [60 + a]]

Объединено с 

[40 + a, 50 + a, 60 + a]

На последнем шаге что-то выглядит следующим образом 

[1, 2, 3] >>= \a -> [40 + a, 50 + a, 60 + a]

Становится 

[41, 51, 61, 42, 52, ... ]

Моя дилемма заключается в том, что тип return $ b * 10 + a кажетсяотличаться от типа [40 + a, 50 + a, 60 + a].

Разве подпись привязки не должна быть такой? 

 (>>=)  :: m a -> (a -> m b) -> m b

В этом примере кажетсябыть как 

[int] -> (int -> [int -> int -> int]) -> [int -> int]

И 

[int] -> (int -> [int -> int]) -> [int]

Ответы [ 3 ]

0 голосов
/ 14 декабря 2018

Имейте ввиду, что return x = [x] и xs >>= f = concatMap f xs в списке монада.Таким образом, 

[1, 2, 3] >>= \a -> 
      ([4, 5, 6] >>= \b -> 
                 return $ b * 10 + a)

превращается в 

concatMap (\a -> (concatMap (\b -> [b*10+a]) [4,5,6])) [1,2,3]

, который становится (с a в качестве свободной переменной в функции b) 

concatMap (\a -> [4*10+a, 5*10+a, 6*10+a]) [1,2,3]

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

[4*10+1, 5*10+1, 6*10+1, 4*10+2, 5*10+2, 6*10+2, 4*10+3, 5*10+3, 6*10+3]

или 

[41,51,61,42,52,62,43,53,63]
0 голосов
/ 15 декабря 2018

Вот как это работает и работает.Вы правы, что это: 

do
  a <- [1, 2, 3]
  b <- [4, 5, 6]
  return $ a * 10 + b

Desugars к этому: 

[1, 2, 3] >>= \a -> 
  [4, 5, 6] >>= \b -> 
    return $ b * 10 + a

Который, в свою очередь, использует экземпляр списка Monad, чьи определения >>= и return (или pure) мы можем встроить: 

concatMap
  (\a -> concatMap
    (\b -> [b * 10 + a])
    [4, 5, 6])
  [1, 2, 3]

Мы можем разбить concatMap на concat и map: 

concat
  (map
    (\a -> concat
      (map
        (\b -> [b * 10 + a])
        [4, 5, 6]))
    [1, 2, 3])

Теперь мы можем уменьшитьэто, и я думаю, что именно здесь вы столкнулись с трудностями: сокращение происходит извне и не дает частично примененных функций в этом случае;скорее, захватывает a в закрытии внутренней лямбды (\b -> …).Сначала мы отображаем (\a -> …) поверх [1, 2, 3]: 

concat
  [ (\a -> concat
      (map
        (\b -> [b * 10 + a])
        [4, 5, 6])) 1
  , (\a -> concat
      (map
        (\b -> [b * 10 + a])
        [4, 5, 6])) 2
  , (\a -> concat
      (map
        (\b -> [b * 10 + a])
        [4, 5, 6])) 3
  ]

==

concat
  [ let a = 1
    in concat
      (map
        (\b -> [b * 10 + a])
        [4, 5, 6])
  , let a = 2
    in concat
      (map
        (\b -> [b * 10 + a])
        [4, 5, 6])
  , let a = 3
    in concat
      (map
        (\b -> [b * 10 + a])
        [4, 5, 6])
  ]

Затем мы можем уменьшить внутренние map s: 

concat
  [ let a = 1
    in concat
      [ (\b -> [b * 10 + a]) 4
      , (\b -> [b * 10 + a]) 5
      , (\b -> [b * 10 + a]) 6
      ]
  , let a = 2
    in concat
      [ (\b -> [b * 10 + a]) 4
      , (\b -> [b * 10 + a]) 5
      , (\b -> [b * 10 + a]) 6
      ]
  , let a = 3
    in concat
      [ (\b -> [b * 10 + a]) 4
      , (\b -> [b * 10 + a]) 5
      , (\b -> [b * 10 + a]) 6
      ]
  ]

==

concat
  [ let a = 1
    in concat
      [ let b = 4 in [b * 10 + a]
      , let b = 5 in [b * 10 + a]
      , let b = 6 in [b * 10 + a]
      ]
  , let a = 2
    in concat
      [ let b = 4 in [b * 10 + a]
      , let b = 5 in [b * 10 + a]
      , let b = 6 in [b * 10 + a]
      ]
  , let a = 3
    in concat
      [ let b = 4 in [b * 10 + a]
      , let b = 5 in [b * 10 + a]
      , let b = 6 in [b * 10 + a]
      ]
  ]

, которые мы можем затем упростить, заменив переменные наих значения: 

concat
  [ concat
    [ [4 * 10 + 1]
    , [5 * 10 + 1]
    , [6 * 10 + 1]
    ]
  , concat
    [ [4 * 10 + 2]
    , [5 * 10 + 2]
    , [6 * 10 + 2]
    ]
  , concat
    [ [4 * 10 + 3]
    , [5 * 10 + 3]
    , [6 * 10 + 3]
    ]
  ]

и сокращение вызовов до concat: 

concat
  [ [ 4 * 10 + 1
    , 5 * 10 + 1
    , 6 * 10 + 1
    ]
  , [ 4 * 10 + 2
    , 5 * 10 + 2
    , 6 * 10 + 2
    ]
  , [ 4 * 10 + 3
    , 5 * 10 + 3
    , 6 * 10 + 3
    ]
  ]

==

[ 4 * 10 + 1
, 5 * 10 + 1
, 6 * 10 + 1
, 4 * 10 + 2
, 5 * 10 + 2
, 6 * 10 + 2
, 4 * 10 + 3
, 5 * 10 + 3
, 6 * 10 + 3
]

И, конечно, отдельные выражения: 

[ 41, 51, 61
, 42, 52, 62
, 43, 53, 63
]

Случай, когда вы будет видеть список частично примененных функций при использовании экземпляра Applicative списков, например, эквивалент вашего кода: 

(\a b -> b * 10 + a) <$> [1, 2, 3] <*> [4, 5, 6]

Определение <$> /fmap для списков - просто map, поэтому мы частично применяем первый аргумент лямбда-выражения, получая список типа [Int -> Int], затем (<*>) :: (Applicative f) => f (a -> b) -> f a -> f b, здесь, в типе [Int -> Int] -> [Int] -> [Int], применяет каждую функцию в своем левом операндекаждому значению в правом операнде.

0 голосов
/ 14 декабря 2018

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

[1, 2, 3] >>= \a -> (...)

Для каждого элемента в списке как-нибудь создайте список с доступом к a в качестве имени для элемента в исходном списке

... [4, 5, 6] >>= \b -> (...)

Чтобы создать список, необходимый для предыдущего шага, создайте новый список с доступом к a и b, по одному из каждого из двух нумерованных списков. 

... return $ b * 10 + a

Чтобы создать список, необходимый для предыдущего шага, создайте список из одного элемента со значением b * 10 + a.

Вы спрашиваете, почему тип return $ b * 10 + a отличается от типа [40 + a, 50 + a, 60 + a], но это не так: оба типа [Int].Ни один не включает никаких функций.Скорее, они оба представляют собой списки чисел, построенные путем обращения к уже замкнутым переменным.И действительно, (>>=) имеет именно тот тип, который должен: он принимает список int и функцию для создания списка int из одного int и возвращает другой список int: 

(>>=) :: [Int] -> (Int -> [Int]) -> [Int]
...