多次使用++:如果我从右到左强制进行评估,效率更高？

Question

我想在一个表达式中一次附加3个或更多列表.

a ++ b ++ c

将从左到右或从右到左评估++运算符？

1. (a ++ b) ++ c
2. a ++ (b ++ c)

我会说选项2,因为如果++是一个前缀函数,我们会写++ a ++ b c自然导致++ b c首先进行评估.我不确定我是否正确.

但如果它是选项1,在我看来,从右到左明确地改变评估顺序更有效:

a ++ (b ++ c)

原因如下:a ++ b ++ c将首先评估为ab ++ cn个步骤(其中n是a的长度,ab当然是a和b的连接)然后再进行abcn + m个步骤(m是b的长度,因此n + m是ab)的长度,总共2n + m步.然而,a ++ (b ++ c)首先评估为a ++ bcm步骤,然后再进行abcn个步骤,这仅仅是n + m个步骤.

我是哈斯凯尔的新手,不知道我在说什么,我想要一些确认.

Answer 1

a ++ b ++ c

被解析为

a ++ (b ++ c)

正是由于你描述的原因:(++)已经左联,然后a ++ b ++ c会复制a两次.你可以在GHCi中查看

Prelude> :i (++)

会回应

infixr 5 ++

其中的infixr意思是"中缀,右联".

Answer 2

从ghci,做一个:i:

Prelude> :i (++)
(++) :: [a] -> [a] -> [a]   -- Defined in GHC.Base
infixr 5 ++

这表明它++是(中缀和)右关联,并将从右到左进行评估.我不知道,但是我愿意打赌,当他/她做出正确联想时,实施该问题的人都会考虑到你的问题.