再帰をfoldrで書き換えて確認

Haskellの実験メモです。

再帰をfoldrで書き換えた実装が同じ動きをするかどうか、ランダムデータで確認しました。

自前で乱数生成せずにQuickCheckを使うべき、というかそもそも定理証明支援系を使うべきなんでしょうけど。

import System.Random
import Control.Monad

shuffle [] = return []
shuffle xs = do
    n <- getStdRandom $ randomR (0, length xs - 1) :: IO Int
    xs' <- shuffle $ take n xs ++ drop (n + 1) xs
    return $ (xs !! n) : xs'

bswap [x] = [x]
bswap (x:xs)
    | x > y     = y:x:ys
    | otherwise = x:y:ys
    where
        (y:ys) = bswap xs

bswap' = foldr (\x xs -> case xs of
    [] -> [x]
    (y:ys) | x > y     -> y:x:ys
           | otherwise -> x:y:ys) []

main = do
    a <- forM [1..1000] $ \_ -> do
        len <- getStdRandom $ randomR (5, 200) :: IO Int
        xs <- shuffle [1..len]
        let a  = bswap  xs
            a' = bswap' xs
        --print (a == a', xs, a, a')
        return $ if a == a' then 1 else 0
    let ok = sum a
        ng = length a - ok
    putStrLn $ "OK: " ++ show ok ++ ", NG: " ++ show ng

実行結果

OK: 1000, NG: 0