我如何编码我的应用程序有状态计算？

Question

假设我有一个包含少量关联对的Traversable数据( (Index, Fruit) )

type Index = Int
data Fruit = Apple | Orange | Tomato

defaultFruit = Tomato

convertFruits :: (Traversable t) => t (Index, Fruit) -> Int -> [Fruit]
convertFruits input n = undefined

convertFruits应该返回一个长度n列表，其中填充了Tomatos，除了input包含具有匹配索引的关联对的所有位置--在这种情况下，来自input的匹配Fruit放在匹配索引处。

预期产出实例：

convertFruits [] 4 = [Tomato, Tomato, Tomato, Tomato]
convertFruits [(2, Apple)] = [Tomato, Apple, Tomato, Tomato]
convertFruits [(1, Orange), (3, Orange), (4, Apple)] = \
    [Orange, Tomato, Orange, Apple]

我如何定义这样的函数？我能否有效地编码一种纯方法，避免O(n平方)？

我看到有traverse在执行Applicative操作，Applicative看起来很像Monad。但实际上，与好的Monad相比，我对Applicative并不了解。有什么帮助吗？

Answer 1

首先，在这个场景中不需要Traversable，因为您的结果是一个列表。Foldable已经足够好了。让我们暂时忘记这一点。如果您只坚持列表，convertFruits会是什么样子？

import qualified Data.Vector as V
import           Data.Vector ((//))

-- O(n + length input)
convertFruitsList :: [(Index, Fruit)] -> Int -> [Fruit]
convertFruitsList input n = V.toList $ V.replicate n Tomato // input'
  where input' = map (\(ix, f) -> (ix - 1, f)) input
        -- Vector is 0-indexed, so we need to adjust the indices

现在，一个人怎么能为Foldable t (Index, Fruit) -> Int -> [Fruit]做同样的事情呢？这也很简单：

import Data.Foldable (toList, Foldable)

convertFruits :: Foldable t => t (Index, Fruit) -> Int -> [Fruit]
convertFruits input n = convertFruitsList (toList input) n

正如您所看到的，在这个场景中根本没有必要使用traverse或Applicative。

Answer 2

这是对ST monad的完美使用：

import Data.Array.ST
import Data.Array(elems)
import Data.Traversable

type Index = Int
data Fruit = Apple | Orange | Tomato
    deriving Show

defaultFruit = Tomato

convertFruits :: (Traversable t) => t (Index, Fruit) -> Int -> [Fruit]
convertFruits input n = elems $ runSTArray $ do 
    a <- newArray (1,n) defaultFruit
    _ <- for input $ uncurry (writeArray a)
    return a

ST允许您在纯计算中使用可变性来获得有效的O(n)算法。