toyboot4e
こんばんは。2 次元の動的計画法をシュッっと書きたいのですが、 ST モナドなどでハマっています。
お力添えいただけないでしょうか (スレッドに続く) 。
お力添えいただけないでしょうか (スレッドに続く) 。
def run_dp(user_function, bounds):
array := default_2d_array(bounds)
for (y, x) in bounds:
array[y, x] = user_function(array, (y, x))
return arrayIOArray を使うと、似た関数をコンパイルできました (tabulateIO :: forall i e. (Ix i) => (IOArray i e -> i -> IO e) -> (i, i) -> e -> IO (IOArray i e)
tabulateIO f bounds_ e0 = do
tbl <- newArray bounds_ e0 :: IO (IOArray i e)
forM_ (range bounds_) $ \i -> do
e <- f tbl i
writeArray tbl i e
return tblIOUArray を使おうとするとエラーになりました (`newArray` の箇所で Could not deduce (MArray IOUArray e IO))unsafeFreeze するのが手間でした。またIOArray を runSTArray + STArray に置き換えることができませんでしたe の制約が緩い (`Int`, Char など unboxed な型に限定する必要がある？)f の利用が ST モナドの制限に (なぜか) 引っかかるIOUArray への変更は下記のようにできました#!/usr/bin/env stack
{- stack script --resolver lts-16.11
--package array --package bytestring --package containers
--package vector --package vector-algorithms --package primitive --package transformers
-}
{- ORMOLU_DISABLE -}
{-# LANGUAGE BangPatterns, BlockArguments, LambdaCase, MultiWayIf, PatternGuards, TupleSections #-}
{-# LANGUAGE NumDecimals, NumericUnderscores #-}
{-# LANGUAGE FlexibleInstances, MultiParamTypeClasses, ScopedTypeVariables, TypeApplications #-}
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE FlexibleContexts #-}
{- ORMOLU_ENABLE -}
-- {{{ Imports
module Main (main) where
import Control.Monad
import Data.Char
import Data.List
{- ORMOLU_DISABLE -}
-- array
import Data.Array.IArray
import
import Data.Array.MArray
import
import Data.Array.Unsafe
import qualified Data.Array as A
import qualified Data.Array.Unboxed as AU
-- bytestring:
import qualified Data.ByteString.Char8 as BS
-- vector:
import qualified Data.Vector.Unboxed as VU
{- ORMOLU_ENABLE -}
getLineIntList :: IO [Int]
getLineIntList = unfoldr (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine
getLineIntVec :: IO (VU.Vector Int)
getLineIntVec = VU.unfoldr (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine
tabulateIO :: forall i e. (Ix i, MArray IOUArray e IO) => (IOUArray i e -> i -> IO e) -> (i, i) -> e -> IO (IOUArray i e)
tabulateIO f bounds_ e0 = do
-- FIXME: "Could not deduce (MArray IOUArray e IO)" with `IOUArray`
tbl <- newArray bounds_ e0 :: IO (IOUArray i e)
forM_ (range bounds_) $ \i -> do
e <- f tbl i
writeArray tbl i e
return tbl
main :: IO ()
main = do
[nItems, wLimit] <- getLineIntList
wvs <- VU.replicateM nItems $ (\[a, b] -> (a, b)) <$> getLineIntList
let dp = tabulateIO f rng (0 :: Int)
rng = ((0, 0), (nItems, wLimit))
f :: IOUArray (Int, Int) Int -> (Int, Int) -> IO Int
f _ (0, _) = return 0
f tbl (i, w) = do
let wv = wvs VU.! (i - 1)
v1 <- readArray tbl (i - 1, w)
v2 <- if w - fst wv >= 0 then (snd wv +) <$> readArray tbl (i - 1, w - fst wv) else return 0
return $ max v1 v2
dp' <- dp
dp'' <- unsafeFreeze dp' :: IO (AU.UArray (Int, Int) Int)
print $ maximum [dp'' ! (nItems, w) | w <- [0..wLimit]] tabulateIO の MArray IOUArray e IO 制約ですねtabulateIO の型だと e に関する制約がないので指定してやる必要があります1. 型引数eの制約が緩い (`Int`,Charなど unboxed な型に限定する必要がある？)
ST 版はここまで書いて runSTUArray に e は MArray (STUArray s) e (ST s) を満たすよって教えられなかったのでちょっと引数工夫しないといけなさそう（`RankNTypes` 有効）
tabulateIO :: forall i e. (Ix i) => (forall s. MArray (STUArray s) e (ST s) => STUArray s i e -> i -> ST s e) -> (i, i) -> e -> UArray i e
tabulateIO f bounds_ e0 =
runSTUArray uarray
where
uarray :: forall s. MArray (STUArray s) e (ST s) => ST s (STUArray s i e)
uarray = do
-- FIXME: "Could not deduce (MArray IOUArray e IO)" with `IOUArray`
tbl <- newArray bounds_ e0 :: ST s (STUArray s i e)
forM_ (range bounds_) $ \i -> do
e <- f tbl i
writeArray tbl i e
return tblInt にする手もありますねMArray IOUArray e IO Num Int みたいな無意味な制約を加えてキャッキャしてましたST 版の forall s. にとても納得しました。それぞれの関数が任意のライフタイム (state thread?) (の array) に適用できるという感じですねFlexibleContexts や RankNTypes は有効ですが、他の言語拡張が足りなかったりしますか……？ • Could not deduce (MArray (STUArray s) e (ST s))
arising from a use of 'uarray'
from the context: Ix i
bound by the type signature for:
tabulateIO :: forall i e.
Ix i =>
(forall s.
MArray (STUArray s) e (ST s) =>
STUArray s i e -> i -> ST s e)
-> (i, i) -> e -> UArray i e
at /Path/To/atcoder-tessoku-hs/a19/Main.hs:65:1-139
• In the first argument of 'runSTUArray', namely 'uarray'
In the expression: runSTUArray uarray
In an equation for 'tabulateIO':
tabulateIO f bounds_ e0
= runSTUArray uarray
where
uarray ::
forall s. MArray (STUArray s) e (ST s) => ST s (STUArray s i e)
uarray
= do tbl <- ...
....
|
67 | runSTUArray uarray
| ^^^^^^f の型が推論されなかったので、割り切って tabulateST を諦めるのも良い気がしてきました。 Boilerplate と言うほどのコード量でもないですものね)ので、型検査通りませんでした:confounded:ST版はここまで書いてrunSTUArrayにeはMArray (STUArray s) e (ST s)を満たすよって教えられなかった
e をやめて具体的にすれば通ると思いますtabulateST は止めようと思います。ありがとうございます！{-# LANGUAGE QuantifiedConstraints, RankNTypes, FlexibleContexts, ScopedTypeVariables #-}
import
import (ST)
import Data.Array.Unboxed
import Control.Monad (forM_)
tabulateIO :: forall i e. (Ix i, forall s. MArray (STUArray s) e (ST s)) => (forall s. STUArray s i e -> i -> ST s e) -> (i, i) -> e -> UArray i e
tabulateIO f bounds_ e0 =
runSTUArray uarray
where
uarray :: forall s. MArray (STUArray s) e (ST s) => ST s (STUArray s i e)
uarray = do
tbl <- newArray bounds_ e0 :: ST s (STUArray s i e)
forM_ (range bounds_) $ \i -> do
e <- f tbl i
writeArray tbl i e
return tbl tabulateIO :: .. の => を 1 個にして QuantifiedConstraints を有効化)