모나드 관련 문제

Question

'워드 체인'을 생성하는 프로그램을 작성하려고합니다. bat -> cat -> cot -> bot, 모나드 (대부분은 이해력)를 사용하여 단어의 조합을 생성하고, 상태 모나드를 사용하여 가능성을 탐색합니다. 나는 단어가 작동 아래,하지만 당신은 내가 정말이 부분에서 뭘하는지 모르는 볼 수 생성

import Control.Monad.State 

type Word = String 
type Chain = [Word] 

getNext :: Word -> State Chain Word 
getNext word = do 
    list <- get 
    return (list ++ "current word") 

부분 : 그 두 번째 부분은 나에게 문제를주고있다. 기본적으로 wordVariations :: Word -> [Word]은 Word를 사용하고 주어진 단어와 한 문자가 다른 단어 목록을 반환합니다. 나는 각 단어가 선행자를 나타내는 상태가되도록 이것을 바꾸려고한다.

예 : input = "cat".

3 단계 후에 "cat"에서 "got"을 얻을 수 있지만, "cat", "cot", "got" 어떻게 거기에 도착했는지 말해줘.

내가 온라인에서 찾은 State Monad 튜토리얼은 전혀 도움이되지 않았습니다. 위의 코드는, GHC 컴파일 할 때 오류 제공 : 이것은 단지의 떨어져 작동하기위한 테스트로 의미

WordChain.hs:42:11: 
    Couldn't match type `Word' with `Char' 
    When using functional dependencies to combine 
     MonadState s (StateT s m), 
     arising from the dependency `m -> s' 
     in the instance declaration in `Control.Monad.State.Class' 
     MonadState [Char] (StateT Chain Data.Functor.Identity.Identity), 
     arising from a use of `get' at WordChain.hs:42:11-13 
    In a stmt of a 'do' block: list <- get 
    In the expression: 
     do { list <- get; 
      return (list ++ "current word") } 
Failed, modules loaded: none. 

을,하지만 난 그것을 알아낼 수 없습니다!

코드는 다음과 같이 유용합니다. 이것이 이것이 가장 현명한 방법이 아닐 수도 있지만, 모나드에 대해 배울 수있는 좋은 기회입니다. 나는 몇 가지 주요 리팩토링이 요구 될 것이라고 생각하기 때문에 내가 코드도 작동하는 방식에서 필요한 변경을 열어주는 말들 : 모든

import   Control.Monad.State 

type Word = String 
type Dict = [String] 
-- data Chain = Chain [Word] deriving (Show) 

replaceAtIndex :: Int -> a -> [a] -> [a] 
replaceAtIndex n item ls = a ++ (item:b) where (a, (_:b)) = splitAt n ls 

tryLetter str c = [replaceAtIndex n c str | n <- [0..(length str - 1)]] 

wordVariations str = tryLetter str =<< ['a' .. 'z'] 

testDict :: Dict 
testDict = ["cat","cog","cot","dog"] 

------- implement state to record chain 

type Chain = [Word] -- [cat,cot,got,tot], etc. state var. 

startingState = [""] :: Chain 

getNext :: Word -> State Chain Word 
getNext w = do 
    list <- get 
    return (list ++ "current word") 

Answer 1

먼저 게시 된 오류는이 라인 return (list ++ "current word")입니다.

• "current word" 유형 String, which is an alias for [샤아] '별명 인, Word이다.

• 가변 list는 [[Char]]의 별칭 [Word] 별명이다 Chain의 형태를 갖는다.

• 함수의 형식 시그니처는 반환 형식을 Word로 설정해야합니다.

• ++은 양쪽 유형이 같은 유형의 목록 인 (++) :: [a] -> [a] -> [a]이어야합니다.

• 그러나 위의 유형 서명을 연결하면 "a"가 일치하지 않는 [Word] -> [Char] -> [Char] 유형이 표시됩니다.

---

빠른하지만 매우 중요한 성능 측면 참고 : 이전 버전을 구축하고 (사용 :) 그리고 마지막에 그들을 반전 고려할 수 있도록 목록에 붙이는는 훨씬 더 빨리 추가 다음이다.

---

상태 모나드는 실제로 결과에 도달하는 데 사용 된 단계를 저장하기위한 올바른 선택이 아닙니다. List Monad가 작업을 완료하기에 충분할 때 적어도 그것은 과잉 공격입니다.고려 :

-- given a list of words, find all possible subsequent lists of words 
getNext :: [String] -> [[String]] 
getNext words@(newest:_) = fmap (:words) (wordVariations newest) 

-- lazily construct all chains of every length for every word 
wordChains :: String -> [[[String]]] 
wordChains word = chain 
    where chain = [[word]] : map (>>= getNext) chain 

-- all the 5 word long chains starting with the word "bat" 
batchains = wordChains "bat" !! 4 

(면책 조항 : 컴파일되었지만 실행되지 않음).

getNext는 체인을 가져 와서 체인의 목록을 포함하는 목록을 리턴합니다. 여기서 각 목록은 체인의 앞에 다른 후미를 갖습니다. 공통된 꼬리를 공유하기 때문에 이것은 효율적입니다.

wordChains에서 목록 모나드 (>> = getNext)를 사용하여 반복적으로 매핑하면 게으른 무한 목록으로 끝납니다. 여기서 0 번째 항목은 시작 단어이고 첫 번째 항목은 모두 2 개 항목의 체인입니다. 첫 번째 단어는 시작 단어이고 두 번째 항목은 모두 3 개의 항목 체인입니다. 길이가 5 인 체인 하나만 있으면 4 번째 아이템의 머리 부분을 잡을 수 있습니다.이 아이템을 생성하기에 충분한 계산이 이루어 지지만 모든 아이템을 얻을 수도 있습니다.

또한 getNext는 필터링을 통해 단어를 반복하지 않도록 확장 될 수 있습니다. 이 wordVariations를 찾는에 관해서

---

마지막으로, 또 다른 알고리즘은 두 단어의 길이가 같은 그들 사이에 다른 문자 수를 경우 1 정확히 True를 반환하는 필터를 구성하는 것입니다. 그러면 가능한 모든 문자 변형을 시도하는 대신 사전을 필터링 할 수 있습니다.

행운을 빈다.