有没有办法在Haskell中优雅地表示这种模式？

Question

用一种命令式语言来思考下面的纯函数:

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永远不应再使用's值,但它仍然可以.如果您不小心使用它,那将是一个未检测到的错误.

我已经设法使用State monad解决了这个问题:

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.

那么:什么是表达这种模式的更具可读性,优雅和安全的方式？

完整的测试代码.

Answer 1

你的目标

虽然命令式代码的直接转换通常会导致STmonad STRef,但让我们考虑一下你真正想做的事情:

1. 您希望有条件地操纵值.
2. 您想要返回该值.
3. 您想要对操作的步骤进行排序.

要求

现在这确实看起来像是STmonad.但是,如果我们遵循简单的monad法则和do符号,我们就会看到

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

正是你想要的.由于您只需要monad(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表达式与结果表达式明显不同,后者将在右侧的lambda中使用.

助手

为了使这更清楚,你可以添加帮助器

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)

但最重要的是,Identitymonad拥有你完成这项任务所需的一切.

势在必行或非命令性

人们可能会争论这种风格是否必要.这绝对是一系列行动.但除非你计算绑定变量,否则没有状态.但是,然后一包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)

摆脱最简单的monad

但是,如果我们(?)在左侧使用并删除returns,我们可以(>>=) :: 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)

这与do上面的desugared 表达非常相似.请注意,任何用法Identity都可以转换为此样式,反之亦然.

Answer 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''

Answer 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

Answer 4

这是ST(状态变换器)库的工作.

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

我们可以定义以下帮助程序来匹配Python样式示例使用的命令式操作,而不是使用低级别readSTRef和writeSTRef整个地方foo:

-- 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计算的值分配给xSTRef ref.
• (f $: ref)将纯函数f应用于STRef ref.
• action `if_` guardaction仅在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)

注意事项:

• 虽然我们首先要定义一些语法佣工(=:,$:,if_翻译之前)foo,这说明了如何使用ST和STRef作为成长多数民众赞成直接手头适合的问题你自己的小命令式语言基础.
• 除了语法之外,这与原始命令式定义的结构完全匹配,没有任何容易出错的重组.对原始示例的任何微小更改都可以直接镜像到Haskell.(x' <- readSTRef x在Haskell代码中添加临时绑定只是为了将它与原生的if/else语法一起使用:如果需要,可以用适当的基于ST的if/else构造替换它.)
• 上面的代码演示了为同一计算提供纯接口和有状态接口:纯调用者可以在foo不知道它内部使用可变状态的情况下使用,而ST调用者可以直接使用fooST(例如,为其提供现有的STRef进行修改).

Answer 5

@Sibi在评论中说得最好:

我建议你不要再强调思考,而是要以功能的方式思考.我同意需要一些时间来适应新模式,但尝试将命令式思想转化为函数式语言并不是一个好方法.

实际上,你的连锁店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 then g else h"的结果.

继续进行模式识别,您应该将应用于变量的转换分解为子lambda(或者您在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只能在整个定义中引用一个值(或辅助函数),以便您的代码可以更容易地被推理并证明是正确的.

如果你不给他们有意义的名称(而相反地给你的代码有意义的结构),那么你在哈斯克尔的全部目的错过了.

(恕我直言,到目前为止,其他答案,引用单子和其他恶作剧,正在咆哮错误的树.)