'1부터 10까지의 홀수를 반대 순서로 표시하기'할게요.

제목.

제목의 제목에 대해 갖은 망상을 하고 제멋대로 만든 퍼즐.
【제목】: 목록xs :: [a]과 요소와 관련된 술어p :: a -> Bool를 제시했을 때 이른바 xs 정의는 p만 만족시키는 요소의 출현 순서가 뒤바뀐 목록의 함수revocc :: (a -> Bool) -> [a] -> [a]를 되돌려준다.단, 반드시 다음과 같은 두 가지 조건을 만족시켜야 한다.

\begin{array}{l}\mathit{revocc}\;\mathit{xs}\in\mathit{permutations}\;\mathit{xs}\end{array}

\begin{array}{l}\mathit{reverse}\cdot\mathit{map}\;\mathit{fst}\cdot\mathit{filter}\; (p\cdot\mathit{snd})\cdot\mathit{zip}\; [0 ..]\\\equiv\\\mathit{map}\;\mathit{fst}\cdot\mathit{filter}\; (p\cdot\mathit{snd}) \cdot\mathit{revocc}\; (p\cdot\mathit{snd})\cdot\mathit{zip}\; [0 ..]\end{array}

코드

module RevOcc where

import Data.Bool ( bool )
import Data.List ( mapAccumL )

소박판

소박판, 사용mapAccumL으로 솔직하게 쓸 수 있습니다.
수수한 버전

-- | Simple version
revocc2 :: (a -> Bool) -> [a] -> [a]
revocc2 p xs = snd $ mapAccumL phi (foldl snoc [] xs) xs
    where
        snoc as b = bool as (b : as) (p b)
        phi as b  = bool (as, b) (tail as, head as) (p b)

일판

1회판은 리프민의 기교를 사용하면 쓸 수 있다.
1회 버전

-- | 1 pass version
revocc1 :: (a -> Bool) -> [a] -> [a]
revocc1 p xs = zs
    where
        (ys, zs) = replace [] ys xs
        replace as ys [] = (as, [])
        replace as ys (z:zs)
            | p z       = case replace (z : as) (tail ys) zs of
                (as', zs') -> (as', head ys : zs')
            | otherwise = case replace as ys zs of
                (as', zs') -> (as', z : zs')

1회판 퍼즐로 즐기세요.어려운 것에 적응하는 성능이 향상된 것도 아니고...