Есть ли способ элегантно представить этот шаблон в Haskell?

Обратите внимание на чистую функцию ниже, на императивном языке:

def foo(x,y):
    x = f(x) if a(x)
    if c(x): 
        x = g(x)
    else:
        x = h(x)
    x = f(x)
    y = f(y) if a(y)
    x = g(x) if b(y)
    return [x,y]

Эта функция представляет собой стиль, в котором вы должны постепенно обновлять переменные. В большинстве случаев этого можно избежать, но бывают ситуации, когда эта схема неизбежна - например, написание процедуры приготовления для робота, которая по своей сути требует серии шагов и решений. Теперь представьте, что мы пытались представить foo в Haskell.

foo x0 y0 =
    let x1 = if a x0 then f x0 else x0 in
    let x2 = if c x1 then g x1 else h x1 in
    let x3 = f x2 in
    let y1 = if a y0 then f y0 else y0 in
    let x4 = if b y1 then g x3 else x3 in
    [x4,y1]

Этот код работает, но он слишком сложный и подвержен ошибкам из-за необходимости ручного управления числовыми тегами. Обратите внимание, что после x1 значение x0 никогда не должно использоваться снова, но оно все еще может. Если вы случайно его используете, это будет необнаруженная ошибка.

Мне удалось решить эту проблему, используя государственную монаду:

fooSt x y = execState (do
    (x,y) <- get
    when (a x) (put (f x, y))
    (x,y) <- get
    if c x 
        then put (g x, y) 
        else put (h x, y)
    (x,y) <- get
    put (f x, y)
    (x,y) <- get
    when (a y) (put (x, f y))
    (x,y) <- get
    when (b y) (put (g x, x))) (x,y)

Таким образом, необходимость отслеживания меток уходит, а также риск случайного использования устаревшей переменной. Но теперь код достаточно подробный и гораздо сложнее понять, в основном из-за повторения (x,y) <- get.

Итак: что является более читаемым, элегантным и безопасным способом выражения этого шаблона?

Полный код для тестирования.

Ответ 1

Ваши цели

В то время как прямое преобразование императивного кода обычно приводит к монаде ST и STRef, давайте подумаем о том, что вы на самом деле хотите сделать:

Вы хотите условно манипулировать значениями.
Вы хотите вернуть это значение.
Вы хотите выполнить последовательность действий.

Требования

Теперь это действительно выглядит сначала как монада ST. Однако, если следовать простым законам монады, вместе с обозначением do, мы видим, что

do 
   x <- return $ if somePredicate x then g x
                                    else h x
   x <- return $ if someOtherPredicate x then a x
                                         else b x

- это именно то, что вы хотите. Поскольку вам нужны только самые основные функции монады (return и >>=), вы можете использовать простейшие:

Монада `Identity`

foo x y = runIdentity $ do
    x <- return $ if a x then f x
                         else x
    x <- return $ if c x then g x
                         else h x
    x <- return $ f x 
    y <- return $ if a x then f y
                         else y
    x <- return $ if b y then g x
                         else y
    return (x,y)

Обратите внимание, что вы не можете использовать let x = if a x then f x else x, потому что в этом случае x будет одинаковым с обеих сторон, тогда как

x <- return $ if a x then f x 
                     else x

совпадает с

(return $ if a x then (f x) else x) >>= \x -> ...

а выражение x в выражении if явно не совпадает с результатом, который будет использоваться в лямбда с правой стороны.

Помощники

Чтобы сделать это более понятным, вы можете добавить помощников, например

condM :: Monad m => Bool -> a -> a -> m a
condM p a b = return $ if p then a else b

чтобы получить еще более сжатую версию:

foo x y = runIdentity $ do
    x <- condM (a x) (f x) x
    x <- fmap f $ condM (c x) (g x) (h x)    
    y <- condM (a y) (f y) y
    x <- condM (b y) (g x) x
    return (x , y)

Терническое безумие

И пока мы справляемся с этим, давайте прокрутить сумасшествие и ввести тройного оператора:

(?) :: Bool -> (a, a) -> a
b ? ie = if b then fst ie else snd ie

(??) :: Monad m => Bool -> (a, a) -> m a
(??) p = return . (?) p

(#) :: a -> a -> (a, a)
(#) = (,)

infixr 2 ??
infixr 2 #
infixr 2 ?

foo x y = runIdentity $ do
    x <- a x ?? f x # x
    x <- fmap f $ c x ?? g x # h x
    y <- a y ?? f y # y
    x <- b y ?? g x # x
    return (x , y)

Но основная идея заключается в том, что в монаде Identity есть все, что вам нужно для этой задачи.

Императивный или не императивный

Можно утверждать, нужен ли этот стиль. Это определенно последовательность действий. Но нет состояния, если вы не подсчитаете связанные переменные. Однако тогда пакет объявлений let … in … также дает неявную последовательность: вы ожидаете, что первая let будет привязана первой.

Использование `Identity` является чисто функциональным

В любом случае приведенный выше код не вводит изменчивость. x не изменяется, вместо этого у вас есть новый x или y затенение последнего. Это становится ясным, если вы обесцениваете выражение do, как указано выше:

foo x y = runIdentity $
      a x ?? f x # x   >>= \x ->
      c x ?? g x # h x >>= \x ->
      return (f x)     >>= \x ->
      a y ?? f y # y   >>= \y ->
      b y ?? g x # x   >>= \x ->
      return (x , y)

Избавление от самой простой монады

Однако, если мы будем использовать (?) в левой части и удалим return s, мы можем заменить (>>=) :: m a -> (a -> m b) -> m b) на что-то с типом a -> (a -> b) -> b. Это просто flip ($). В итоге получим:

($>) :: a -> (a -> b) -> b
($>) = flip ($)     
infixr 0 $> -- same infix as ($)

foo x y = a x ? f x # x   $> \x ->
          c x ? g x # h x $> \x ->
          f x             $> \x ->
          a y ? f y # y   $> \y ->
          b y ? g x # x   $> \x ->
          (x, y)

Это очень похоже на выражение desugared do выше. Обратите внимание, что любое использование Identity может быть преобразовано в этот стиль и наоборот.

Ответ 2

Проблема, которую вы заявляете, выглядит как приятное приложение для стрелки:

import Control.Arrow

if' :: (a -> Bool) -> (a -> a) -> (a -> a) -> a -> a
if' p f g x = if p x then f x else g x

foo2 :: (Int,Int) -> (Int,Int)
foo2 = first (if' c g h . if' a f id) >>>
       first f >>>
       second (if' a f id) >>>
       (\(x,y) -> (if b y then g x else x , y))

в частности, first поднимает функцию a -> b до (a,c) -> (b,c), что более идиоматично.

Изменить: if' разрешает подъем

import Control.Applicative (liftA3)

-- a functional if for lifting
if'' b x y = if b then x else y

if' :: (a -> Bool) -> (a -> a) -> (a -> a) -> a -> a
if' = liftA3 if''

Ответ 3

Я бы, наверное, сделал что-то вроде этого:

foo x y = ( x', y' )
  where x' = bgf y' . cgh . af $ x
        y' = af y

af z    = (if a z then f else id) z
cgh z   = (if c z then g else h) z
bg y x  = (if b y then g else id) x

Для чего-то более сложного, вы можете рассмотреть возможность использования объектива:

whenM :: Monad m => m Bool -> m () -> m ()
whenM c a = c >>= \res -> when res a

ifM :: Monad m => m Bool -> m a -> m a -> m a
ifM mb ml mr = mb >>= \b -> if b then ml else mr

foo :: Int -> Int -> (Int, Int)
foo = curry . execState $ do
  whenM (uses _1 a) $ 
    _1 %= f

  ifM (uses _1 c)
    (_1 %= g)
    (_1 %= h)

  _1 %= f

  whenM (uses _2 a) $ 
    _2 %= f

  whenM (uses _2 b) $ do
    _1 %= g

И ничто не мешает вам использовать более описательные имена переменных:

foo :: Int -> Int -> (Int, Int)
foo = curry . execState $ do
  let x :: Lens (a, c) (b, c) a b
      x = _1
      y :: Lens (c, a) (c, b) a b
      y = _2

  whenM (uses x a) $ 
    x %= f

  ifM (uses x c)
    (x %= g)
    (x %= h)

  x %= f

  whenM (uses y a) $ 
    y %= f

  whenM (uses y b) $ do
    x %= g

Ответ 4

Это задание для библиотеки ST (state transformer).

ST обеспечивает:

Вычисления с учетом состояния в виде типа ST. Они выглядят как ST s a для вычисления, которое приводит к значению типа a и может выполняться с runST для получения чистого значения a.
Первичные изменчивые ссылки в форме STRef, Действие newSTRef a создает новую ссылку STRef s a с начальным значением a и которая может быть считана с помощью readSTRef ref и написана с помощью writeSTRef ref a. Одно ST-вычисление может использовать любое количество ссылок STRef внутри.

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

Чтобы использовать ST и STRef, нам нужно импортировать:

{-# LANGUAGE NoMonomorphismRestriction #-}
import Control.Monad.ST.Safe
import Data.STRef

Вместо использования низкоуровневых readSTRef и writeSTRef по всему месту мы можем определить следующие помощники, чтобы соответствовать императивным операциям, которые использует пример foo в стиле Python:

-- STRef assignment.
(=:) :: STRef s a -> ST s a -> ST s ()
ref =: x  =  writeSTRef ref =<< x

-- STRef function application.
($:) :: (a -> b) -> STRef s a -> ST s b
f $: ref  =  f `fmap` readSTRef ref

-- Postfix guard syntax.
if_ :: Monad m => m () -> m Bool -> m ()
action `if_` guard  =  act' =<< guard
    where act' b = if b then action
                        else return ()

Это позволяет нам написать:

ref =: x, чтобы присвоить значение ST-вычисления x STRef ref.
(f $: ref) применить чистую функцию f к STRef ref.
action `if_` guard выполнить action, только если guard приведет к True.

С помощью этих помощников мы с готовностью можем перевести исходное императивное определение foo в Haskell:

a = (< 10)
b = even
c = odd
f x = x + 3
g x = x * 2
h x = x - 1
f3 x = x + 2

-- A stateful computation that takes two integer STRefs and result in a final [x,y].
fooST :: Integral n => STRef s n -> STRef s n -> ST s [n]
fooST x y = do
    x =: (f $: x) `if_` (a $: x)

    x' <- readSTRef x
    if c x' then
        x =: (g $: x)
    else
        x =: (h $: x)

    x =: (f $: x)
    y =: (f $: y) `if_` (a $: y)
    x =: (g $: x) `if_` (b $: y)

    sequence [readSTRef x, readSTRef y]

-- Pure wrapper: simply call fooST with two fresh references, and run it.
foo :: Integral n => n -> n -> [n]
foo x y = runST $ do
    x' <- newSTRef x
    y' <- newSTRef y
    fooST x' y'

-- This will print "[9,3]".
main = print (foo 0 0)

Примечание:

Прежде чем перевести foo, мы сначала должны были определить некоторые синтаксические помощники (=:, $:, if_), это демонстрирует, как вы можете использовать ST и STRef в качестве основы для создания собственного небольшого императивного языка что непосредственно подходит к проблеме.
Синтаксис в стороне, это точно соответствует структуре первоначального императивного определения без какой-либо подверженной ошибкам реструктуризации. Любые незначительные изменения исходного примера могут быть зеркально отображены непосредственно в Haskell. (Добавление временного связывания x' <- readSTRef x в коде Haskell только для того, чтобы использовать его с родным синтаксисом if/else: при желании это можно заменить соответствующей конструкцией if/else на основе ST.)
Вышеприведенный код демонстрирует предоставление как чистых, так и согласованных состояний интерфейсов для одного и того же вычисления: чистые абоненты могут использовать foo, не зная, что он использует изменчивое состояние внутри, а ST вызывающие могут напрямую использовать fooST (и, например, предоставляют это с существующими STREF для изменения).

Ответ 5

@Сиби сказал это лучше всего в своем комментарии:

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

Практически говоря, ваша цепочка let может быть хорошей отправной точкой:

foo x0 y0 =
    let x1 = if a x0 then f x0 else x0 in
    let x2 = if c x1 then g x1 else h x1 in
    let x3 = f x2 in
    let y1 = if a y0 then f y0 else y0 in
    let x4 = if b y1 then g x3 else x3 in
    [x4,y1]

Но я бы предложил использовать один let и дать описательные имена промежуточным этапам.

В этом примере, к сожалению, я не знаю, что делают различные x и y, поэтому я не могу предложить значимые имена. В реальном коде вы должны использовать имена, такие как x_normalized, x_translated или такие, а не x1 и x2, чтобы описать, каковы эти значения.

Фактически, в let или where у вас действительно нет переменных: это просто сокращенные имена, которые вы даете промежуточным результатам, чтобы было легко составить окончательное выражение (после in или до where.)

Это дух ниже x_bar и x_baz ниже. Попробуйте придумать имена, которые достаточно понятны, учитывая контекст вашего кода.

foo x y =
    let x_bar   = if a x then f x else x
        x_baz   = f if c x_bar then g x_bar else h x_bar
        y_bar   = if a y then f y else y
        x_there = if b y_bar then g x_baz else x_baz
    in  [x_there, y_bar]

Затем вы можете начать распознавать шаблоны, которые были скрыты в императивном коде. Например, x_bar и y_bar представляют собой в основном одно и то же преобразование, применяемое соответственно к x и y: почему они имеют такой же суффикс "_bar" в этом бессмысленном примере; то ваш x2, вероятно, не нуждается в промежуточном имени, так как вы можете просто применить f к результату целого "if c, а затем g else h".

Продолжая распознавание образов, вы должны разложить преобразования, которые вы применяете к переменным, в sub-lambdas (или что-то другое, что вы называете вспомогательными функциями, определенными в предложении where.)

Опять же, я не знаю, что сделал исходный код, поэтому я не могу предложить значимые имена для вспомогательных функций. В реальном приложении f_if_a будет называться normalize_if_needed или thaw_if_frozen или mow_if_overgrown... вы получите идею:

foo x y =
    let x_bar   = f_if_a x
        y_bar   = f_if_a y
        x_baz   = f (g_if_c_else_h x_bar)
        x_there = g_if_b x_baz y_bar
    in  [x_there, y_bar]
where
    f_if_a x
        | a x       = f x
        | otherwise = x
    g_if_c_else_h x
        | c x       = g x
        | otherwise = h x
    g_if_b x y
        | b y       = g x
        | otherwise = x

Не игнорируйте этот бизнес именования.

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

Имена, которые вы даете вещам внутри определения функции, независимо от того, представлены ли они как аргументы, let или where, могут ссылаться только на одно значение (или вспомогательную функцию) на протяжении всего определения, так что ваш код может быть более легко обоснованные и обоснованные.

Если вы не дадите им значимые имена (и, наоборот, придаете вашему коду значимую структуру), вы упускаете из виду всю цель Haskell.

(ИМХО, другие ответы до сих пор, цитируя монады и другие махинации, лают неправильное дерево.)

Ответ 6

Я всегда предпочитаю преобразовывать трансформаторы состояния в одно состояние по кортежу: он определенно склоняет вещи, позволяя вам "сфокусироваться" на определенном слое (представления в переменных x и y в нашем случае):

import Control.Monad.Trans.Class
import Control.Monad.Trans.State

foo :: x -> y -> (x, y)
foo x y = 
  (flip runState) y $ (flip execStateT) x $ do
    get >>= \v -> when (a v) (put (f v))
    get >>= \v -> put ((if c v then g else h) v)
    modify f
    lift $ get >>= \v -> when (a v) (put (f v))
    lift get >>= \v -> when (b v) (modify g)

Функция lift позволяет нам сосредоточиться на уровне внутреннего состояния, которое y.