하스켈에있는 단어 카운트 프로그램

Question

나는 다가오는 시험을 위해 공부하고있는 과거의 시험에 나갈 것이고, 몇 가지 질문을 마친 후에 나는 풀 수없는 하나의 질문을 마쳤습니다.

문자열 (또는 [Char])을 취해 String에있는 영어 단어 수의 Int를 반환하는 함수가 필요합니다. 그것은 isWord가 문자열을 취하고 단어가 참인지 거짓인지에 따라 부울을 반환하는 가설적인 함수라고 말합니다. 단어는 왼쪽에서 오른쪽으로 연속되어야합니다. 주어진 예제는 "catalogre"입니다. 그래서, "카탈로그", "귀신"과 "로그" "에서" "고양이", 함수는 범퍼는 그냥, 분명히 늘 일을 생각하고 무엇을 보여주고있다 5.

wordsInString :: [Char] -> Int 
wordsInString [] = 0 
wordsInString x 
    | isWord (take 1 x) 
    | isWord (take 2 x) 

반환해야합니다.

이것은 내가 시작한 방법이며 take 함수를 사용하여 한 번에 각 문자를 증가시킨 다음 시작 문자를 []까지 옮길 수 있다고 생각했지만 그 재귀를 구현하는 방법을 잘 모르겠습니다. 바르게. 누구든지 아이디어가 있거나 나에게 길을 보여줄 수 있다면, 좋을 것입니다.

Answer 1

Data.List에서 subsequences 함수를 찾고 있습니다.

the libraries that come with GHC을 통해 읽는 것이 좋습니다. 특히 기본입니다. 시험에서 이러한 기능을 사용할 수 없더라도 형식 코드의 오른쪽에있는 "출처"링크를 따라 가면서 소스 코드를 읽는 것이 유용하고 가끔은 계몽 적입니다.

---

편집 : 의견이 맞고 Matvey의 답변도 마찬가지입니다. 내 대답을 받아들이지 않고 대신 Matvey를 수락 할 수 있습니다.

Answer 2

당신은 모든 가능한 후보 목록을 가져 오지 inits 및 tails를 사용할 수있는 비 단어에서 단어를 구별하는 방법을 알고있는 경우 :

> :m +Data.List 
> concatMap inits $ tails "catalogre" 
["","c","ca","cat","cata","catal","catalo","catalog","catalogr","catalogre","","a","at","ata","atal","atalo","atalog","atalogr","atalogre","","t","ta","tal","talo","talog","talogr","talogre","","a","al","alo","alog","alogr","alogre","","l","lo","log","logr","logre","","o","og","ogr","ogre","","g","gr","gre","","r","re","","e",""] 

Answer 3

allWordsInString :: [Char] -> [[Char]] 
allWordsInString = filter isWord . concat . map tails . inits 
--         ^^^^^^^^^^^^^^^^^^ or, concatMap tails 

wordsInString :: [Char] -> Int 
wordsInString = length . allWordsInString 

이 될 수 있기 때문에 내가 이런 걸 제안 흥미로운 것은 또한 당신의 주어진 끈에있는 영어 단어인지 알기 위해서입니다.

은 기능 구성입니다. concat :: [[a]] -> [a]은 목록을 평평하게 만듭니다. concat [[1,2], [], [3] == [1,2,3]. inits은 주어진리스트의 모든 가능한 접두어를 접미어로 동일하게 tails을 반환합니다. filter :: (a -> Bool) -> [a] -> [a]은 마지막으로 술어, 목록을 취해 술어를 만족시키는 요소 만 포함하는 목록을 리턴합니다.

Answer 4

그 문제는 다소 모호합니다. 저는 명시 적으로 언급되지 않은 몇 가지 가정을 할 것입니다. 한 단어는 다른 단어의 접두어가 될 수 있으며, 중복되는 단어는 매번 계산됩니다.

그런 다음이 문제를 해결하려면 부분으로 나누십시오. 당신은 이미이 일을 조금 해 봤지만, 코드를 따라하지 않은 것 같습니다. Haskell의 강력한 특징은 코드 구조가 종종 생각의 구조를 따를 것이라는 점입니다.

따라서 테스트 할 모든 부분 문자열을 생성 한 다음 결과를 계산하기로 결정했습니다. 코드로 시작하자.

wordCount :: String -> Int 
wordCount = length . findWords 

findWords :: String -> [String] 
findWords = filter isWord . makeSubstrings 

makeSubstrings :: String -> [String] 
makeSubstrings xs = undefined -- hmm, this isn't clear yet 

확인.그것은 출발점입니다. 문제의 핵심에 도달합니다. 테스트 할 후보 하위 문자열을 어떻게 모두 고를 수 있습니까?

질문에 이미 필요한 아이디어가 나와 있습니다. 작은 조각으로 분해하면 충분히 할 수 있습니다. 문자열의 모든 시작 위치에서 무언가를하고 싶다고 언급했습니다. 그렇다면 각 위치에서 시작하는 문자열을 반환하는 함수를 작성하고 끝까지 이동하는 방법은 어떻습니까? 그것은 논리적 인 첫 걸음처럼 보입니다.

-- for the input "foo", this should return the list ["foo", "oo", "o", ""] 
tails :: String -> [String] 
tails = undefined -- I'll leave this one up to you 

그 이름의 선택은 임의적이지 않습니다. 이미 정확하게 Data.List에있는 기능이 있지만, 어떻게 완료되었는지 직접 확인하고 구현해야합니다.

그러나 분명히 당신은 조각을 가져갈 생각으로 그 모든 접두사를 볼 필요가 있음을 분명히 보았습니다. 따라서 문자열의 모든 접두어를 생성하는 또 다른 함수를 작성하십시오. 또한 Data.List에 inits으로 존재하지만 다시 한 번 직접 작성하십시오. 다른 답변이 보여으로

-- for the input "foo", this should return the list ["", "f", "fo", "foo"] 
inits :: String -> [String] 
inits = undefined - again, this is up to you 

그리고,와 map 및 concat,이, 당신은 makeSubstrings을 구현하는 데 필요한 조각을 추가 할 수 있습니다. 다행히도 필자는 필요한 단계를 추론하는 방법과 코드를 구조화하기 위해 이러한 단계를 사용하는 방법을 실제로 전달할 수있었습니다.

Answer 5

목록을 연결하고 목록의 길이를 계산하고 목록의 꼬리를 감수하고 재귀를 사용하는 것 외에 멋진 Haskell 기능을 사용하지 않는 또 다른 솔루션이 있습니다.

1. 먼저 항목 길이와 일부 문자열을 주어진 함수 candidatesWithLength :: Int -> String -> [String]를 작성하고 다음과 같이 동작하도록 한 후, 그 길이의 모든 항목 목록을 얻을 수 :

   생각은 이것이다 :

   > candidatesWithLength 3 "Foo" 
   ["Foo"] 
   > candidatesWithLength 2 "Foo" 
   ["Fo", "oo"] 
   > candidatesWithLength 1 "Foo" 
   ["F", "o", "o"] 
   

2. 이어서, 상기 candidatesWithLength 함수를 사용하여, 모든 주어진 문자열 "후보"(즉 전위)을 산출하는 기능 candidates :: String -> [String] 물품. 함수는 단순히 길이가 1 인 모든 후보를 길이가 2 인 후보와 길이가 3 인 후보자로 채우는 긴 목록을 작성합니다. 그것은 다음과 같이 동작합니다

   :이있는 경우 당신이 당신의 주어진 isWord 기능은 다음과 같이 거짓 얻을 수있는 모든 일을 건너 뛸 수 있도록
   이

   > candidates "Foo" 
   ["Foo", "Fo", "oo", "F, "o", "o"] 
   

3. , 당신은 반환 목록에 기존 filter 기능을 사용 coud

   : 여기

   > filter isWord (candidates "catalogre") 
   ["catalog", "ogre", "cat", "log", "at"] 
   

너무 많은 멋진 기능을 사용하지 않는 두 가지 방법 candidatesWithLength 및 candidates의 구현입니다

candidatesWithLength :: Int -> String -> [String] 
candidatesWithLength len s 
    | len > (length s) = [] 
    | otherwise  = go s (length s - len + 1) 
    where go _ 0 = [] 
      go s' movesLeft = take len s' : go (tail s') (movesLeft - 1) 

candidates :: String -> [String] 
candidates s = go (length s) 
    where go 0 = [] 
      go itemLength = candidatesWithLength itemLength s ++ go (itemLength - 1)