Избегайте сопоставления с образцом в рекурсии

Рассмотрим этот код, который я использовал для решения проблемы Эйлера 58:

diagNums = go skips 2
    where go (s:skips) x = let x' = x+s
                           in x':go skips (x'+1)

squareDiagDeltas = go diagNums
    where go xs = let (h,r) = splitAt 4 xs
                  in h:go r

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

f n = go [1..n]
    where go [] = (0,0)
          go (x:xs) = let (y,z) = go xs
                      in (y+x, z-x)

по сравнению с красивой и простой рекурсией:

f n = go [1..n]
    where go [] = 0
          go (x:xs) = x+go xs

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

Есть ли способы избежать этого, возможно, используя Applicative или что-то подобное? Или вы считаете этот стиль идиоматичным?


haskell applicative
person firefrorefiddle    schedule 01.06.2013    source источник

Ответы (3)


arrow_upward
6
arrow_downward

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

Однако есть альтернатива. Control.Arrow имеет кучу функций для работы с кортежами. Поскольку стрелка функции -> также является Arrow, все это работает для обычных функций.

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

(***) :: a b c -> a b' c' -> a (b, b') (c, c')

Если мы заменим a на ->, мы получим:

(***) :: (b -> c) -> (b' -> c') -> ((b, b') -> (c, c'))

Таким образом, вы можете объединить (+ x) и (- x) в одну функцию с (+ x) *** (- x). Это будет эквивалентно:

\ (a, b) -> (a + x, b - x)

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

(+ x) *** (\ a -> a - x) $ go xs

Вы, очевидно, можете представить себе использование любого другого оператора, все из которых не столь глупы :).

Честно говоря, я думаю, что эта версия менее читабельна, чем оригинал. Однако в других случаях версия *** может быть более удобочитаемой, поэтому знать о ней полезно. В частности, если бы вы передавали (+ x) *** (- x) в функцию более высокого порядка, а не применяли ее немедленно, я думаю, что версия *** была бы лучше, чем явная лямбда.

person Tikhon Jelvis    schedule 01.06.2013
comment
Может заменить вашу лямбду a на (+(-x)) или (subtract x) или есть какая-то проблема? спасибо! :) - person josejuan; 01.06.2013
comment
@josejuan: Да, вы тоже можете сделать что-то из этого. Я не большой поклонник любого из вариантов: P. - person Tikhon Jelvis; 01.06.2013
comment
Итак, стрелки. Эта мысль пришла мне в голову. И вы правы, все еще неясно, лучше ли он, чем оригинал, но он ответил на мой вопрос наиболее прямо и ясно, поэтому я приму ваш ответ. - person firefrorefiddle; 02.06.2013

arrow_upward
4
arrow_downward

Я согласен с Тихоном Джелвисом, что в вашей версии нет ничего плохого. Как он сказал, использование комбинаторов из Control.Arrow может быть полезно с функциями более высокого порядка. Вы можете написать f, используя складку:

f n = foldr (\x -> (+ x) *** subtract x) (0,0) [1..n]

И если вы действительно хотите избавиться от let в squareDiagDeltas (я не уверен, что хотел бы), вы можете использовать second, потому что вы изменяете только второй элемент кортежа:

squareDiagDeltas = go diagNums
  where go = uncurry (:) . second go . splitAt 4
person raymonad    schedule 01.06.2013
comment
Другой вариант: squareDiagDeltas = unfoldr (Just . splitAt 4) diagNums - person hammar; 01.06.2013
comment
Это забавно и креативно с second go, так что +1, спасибо! - person firefrorefiddle; 02.06.2013

arrow_upward
4
arrow_downward

Я согласен с hammar, unfoldr – это правильный путь.

Вы также можете избавиться от сопоставления с образцом в diagNums:

diagNums = go skips 2
    where go (s:skips) x = let x' = x+s
                           in x':go skips (x'+1)

Из-за рекурсии немного сложно сказать, что здесь происходит, поэтому давайте рассмотрим это подробно.

Допустим skips = s0 : s1 : s2 : s3 : ..., тогда имеем:

diagNums = go skips 2
         = go (s0 : s1 : s2 : s3 : ...) 2 
         = s0+2 : go (s1 : s2 : s3 : ... ) (s0+3)
         = s0+2 : s0+s1+3 : go (s2 : s3 : ... ) (s0+s1+4) 
         = s0+2 : s0+s1+3 : s0+s1+s2+4 : go (s3 : ... ) (s0+s1+s2+5) 
         = s0+2 : s0+s1+3 : s0+s1+s2+4 : s0+s1+s2+s3+5 : go (...) (s0+s1+s2+s3+6)

Это значительно проясняет, что происходит, у нас есть сумма двух последовательностей, которую легко вычислить с помощью zipWith (+):

diagNums = zipWith (+) [2,3,4,5,...] [s0, s0+s1, s0+s1+s2, s0+s1+s2+s3,...]

Итак, теперь нам просто нужно найти лучший способ вычисления частичных сумм skips, который отлично подходит для scanl1:

scanl1 (+) skips = s0 : s0+s1 : s0+s1+s2 : s0+s1+s2+s3 : ...

Оставив (IMO) гораздо более понятное определение для diagNums:

diagNums = zipWith (+) [2..] $ scanl1 (+) skips
person rampion    schedule 01.06.2013