[haskell] 이 단어 기능을 접은 후 후 처리 단계없이 구현할 수 있습니까?

Program / 글쓴이

인쇄물의 Real World Haskell, 4 장, 98 페이지에서words 접기를 사용하여 구현할 수 있는지 묻습니다 .

가능합니까? 그렇지 않다면 왜? 그렇다면 어떻게?

나는 다음과 같이 생각해 냈습니다. 각 비 공백은 출력 목록의 마지막 단어 앞에 붙어야하고 ( otherwise가드 에서 발생합니다 ) 공란에 emtpy 단어를 추가해야합니다. 출력 목록이 이미 (이은으로 처리가없는 경우 if– then– else).

myWords :: String -> [String]
myWords = foldr step [[]]
  where
    step x yss@(y:ys)
      | x == ' ' = if y == "" then yss else "":yss
      | otherwise = (x:y):ys

입력 문자열의 선행 공백으로 인해 문자열의 출력 목록에서 선행 빈 문자열이 하나 생성되므로이 솔루션은 잘못되었습니다.

위의 링크에서 다른 독자를 위해 제안 된 여러 솔루션을 살펴 보았고 많은 솔루션이 내 솔루션과 유사하게 작동하지만 일반적으로 폴드의 출력을 “사후 처리”(예 : tail경우에 따라) 빈 선행 문자열입니다.

다른 접근법은 튜플 (실제로 쌍)을 사용하므로 접힘이 쌍을 처리하고 선행 / 후행 공간을 잘 처리 할 수 ​​있습니다.

이러한 모든 접근 방식에서 foldr(또는 다른 접기, 축소)는 상자에서 최종 출력을 제공하는 기능이 아닙니다. 항상 다른 방법으로 출력을 조정해야합니다.

따라서 초기 질문으로 돌아가서 words폴드를 사용하여 실제로 (후행 / 선행 / 반복 공간을 올바르게 처리하는 방법으로) 구현할 수 있는지 묻습니다 . 접기 를 사용 한다는 것은 접기 기능이 가장 바깥 쪽 기능이어야 함을 의미합니다.

myWords :: String -> [String]
myWords input = foldr step seed input

답변

올바르게 이해하면 요구 사항에 다음이 포함됩니다.

(1) words "a b c" == words " a b c" == ["a", "b", "c"]
(2) words "xa b c" == ["xa", "b", "c"] /= ["x", "a", "b", "c"] == words "x a b c"

이것은 우리가 가질 수 없다는 것을 의미합니다

words = foldr step base

어떤 step및 base.

사실, 우리가 가지고 있다면

words "xa b c"
= def words and foldr
step 'x' (words "a b c")
= (1)
step 'x' (words " a b c")
= def words and foldr
words "x a b c"

그리고 이것은 모순된다 (2).

이후에 사후 처리가 필요합니다 foldr.

답변

@chi에는 words“a”폴드를 사용하여 구현할 수 없다는 훌륭한 주장이 있지만 fold s을 사용 한다고 말했습니다 .

words = filterNull . words1
    where
    filterNull = foldr (\xs -> if null xs then id else (xs:)) []
    words1 = foldr (\c -> if c == ' ' then ([]:) else consHead c) []
    consHead c []       = [[c]]
    consHead c (xs:xss) = (c:xs):xss

가장 바깥 쪽과 가장 안쪽의 기능은 모두 접기입니다. 😉

답변

예. foldrCPS ( Continuation Passing Style )에 머무르면 하나를 사용 하여이 작업을 올바르게 수행 할 수는 있지만 조금 까다로울 수 있습니다 . 나는 chunksOf이전에 특별한 종류의 기능을 보여주었습니다 .

이러한 종류의 접기에서 누산기, 따라서 접기의 결과는 함수이므로 최종 결과를 얻기 위해 식별 종류의 입력에 적용해야합니다. 따라서 여기에서 단일 접기를 사용하고 있고 그 유형에 함수가 포함되어 있기 때문에 최종 처리 단계로 간주 될 수도 있고 그렇지 않을 수도 있습니다. 토론을 엽니 다 🙂

ws :: String -> [String]
ws str = foldr go sf str $ ""
         where
         sf :: String -> [String]
         sf s = if s == " " then [""] else [s]
         go :: Char -> (String -> [String]) -> (String -> [String])
         go c f = \pc -> let (s:ss) = f [c]
                         in case pc of
                            ""        -> dropWhile (== "") (s:ss)
                            otherwise -> case (pc == " ", s == "") of
                                         (True, False)  -> "":s:ss
                                         (True, True)   -> s:ss
                                         otherwise      -> (pc++s):ss

λ> ws "   a  b    c   "
["a","b","c"]

sf : 시작할 초기 기능 값.

go : 반복자 기능

우리는 매번 이전 캐릭터 pc와 올바른 캐릭터 c를 모두 가지고 있기 때문에 실제로 CPS의 힘을 충분히 활용하지 못하고 있습니다. 오름차순 요소가 끊어 질 때마다 chunksOfa [Int]를 청킹하면서 위에서 언급 한 기능 에 매우 유용했습니다 [[Int]].

답변