Очистка кода изменяемой матрицы

Question

Я пытаюсь решить проблему MINFREE в «Жемчужинах функционального алгоритма» с использованием изменяемых массивов. Проблема заключается в следующем: учитывая список натуральных чисел n, найдите наименьшее натуральное число, которое не отображается в списке. Я уверен, что следующее решение:

minFree2 :: [Int] -> Int 
minFree2 ns = (fromMaybe 0 $ elemIndex True seen) 
    where 
    bound = (1, length ns) 
    seen = elems $ runSTArray $ do 
     arr <- newSTArray bound False 
     mapM_ (\n -> writeArray arr n False) ns 
     return arr 

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

я могу получить, насколько следующее (перезапись только пункт where):

bound = (1, length ns) 
setTrues arr = mapM_ (flip (writeArray arr) False) ns 
seen = elems $ runSTArray $ newSTArray bound False >>= setTrues 

Но это не работает, потому что она возвращает (), а не STArray s i e. Я хотел бы написать что-то вроде:

setTrues arr = mapM_ (flip (writeArray arr) False) ns >> arr 

таким же образом я мог бы написать fn arr => map ....; arr в SML, но это не работает, потому что здесь arr является STArray s i e, а не ST s (STarray s i e). Я бы ожидать, чтобы быть в состоянии исправить, обернув arr обратно в ST, но моя попытка с:

setTrues arr = mapM_ (flip (writeArray arr) False) ns >> arr 
    seen = elems $ runSTArray $ newSTArray bound False >>= return . setTrues 

Вырабатывает ошибку:

No instance for (MArray (STArray s) Bool (STArray s Int)) 
    arising from a use of `setTrues' 

который я не совсем понимаю.

Есть ли хороший способ написать этот код, сводя к минимуму использование do?

Answer 1

Это должно работать:

setTrues arr = mapM_ (flip (writeArray arr) False) ns >> return arr 
seen = elems $ runSTArray $ newSTArray bound False >>= setTrues 

Хитрость выпускающая setTrues возвращение массива вместо (), как вы уже пытались.

Answer 2

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

accumArray :: Ix i => (e -> a -> e) -> e -> (i, i) -> [(i, a)] -> Array i e 

из Data.Array. Фактически, фактическая реализация этой функции выглядит несколько похожей на ваш код.

В целом, более функциональное решение может выглядеть следующим образом:

minFree2 :: [Int] -> Int 
minFree2 ns = fromMaybe 0 $ elemIndex False $ elems seen 
    where 
    bound = (1, length ns) 
    seen :: Array Int Bool 
    seen = accumArray (||) False bound $ map (,True) ns 

PS: True и False казалось распределены немного неправильно. Я молча зафиксировал это.