최대 목록 및 발생 횟수를 반환하는 함수

Question

나는 재귀 함수 mxAndC을 작성하고 있습니다. 목록을 줄 때 튜플을 반환해야합니다. 튜플은 첫 번째 요소로 지정된 목록의 최대 값을 가지며 두 번째 요소는 요소가 목록에서 발생한 횟수입니다. 할당으로 도우미 함수를 만들 수 없습니다.

mxAdC "bananas" = (s,1) 

mxAdC "banana" =(n,2) 

mxAdC [mod x 4 | x <- [1..50]] -> (3,12) 

나는 다음과 같은 한 :

mxAdC = go 0 
where go count (x:xs) 
      | count /= 0  = (mx, count) 
      | null ((x:xs)) = error "The list is empty" 
      | x == mx   = go (count+1) xs 
     where mx = maximum (x:xs) 

을 그리고 오류를 받고 있어요 : I 출력 다음과 같은 기대하고 있습니다

* Ambiguous type variable `a0' arising from a use of `go' 
     prevents the constraint `(Ord a0)' from being solved. 
     Relevant bindings include 
     mxAdC :: [a0] -> (a0, Integer) (bound at hw06.hs:24:1) 
     Probable fix: use a type annotation to specify what `a0' should be. 
     These potential instances exist: 
     instance (Ord a, Ord b) => Ord (Either a b) 
      -- Defined in `Data.Either' 
     instance Ord Ordering -- Defined in `GHC.Classes' 
     instance Ord Integer 
      -- Defined in `integer-gmp-1.0.0.1:GHC.Integer.Type' 
     ...plus 23 others 
     ...plus 38 instances involving out-of-scope types 
     (use -fprint-potential-instances to see them all) 
    * In the expression: go 0 
     In an equation for `mxAdC': 
      mxAdC 
      = go 0 
      where 
       go count (x : xs) 
        | count /= 0 = (mx, count) 
        | null ((x : xs)) = error "The list is empty" 
        | x == mx = go (count + 1) xs 
        where 
         mx = maximum (x : xs) 

나는 하스켈에서 아주 새로운 해요. 자비로운 전문가가 밖에 나가서이 초보자를 도와 주겠습니까?

Answer 1

상당히 간단 구현 filter을 사용 :

mxAdC :: Ord a => [a] -> (a,Int) 
mxAdC xs = (mx,length $ filter (\x -> x == mx) xs) where mx = maximum xs 

Answer 2

두려운 단일체 제한을 두드렸습니다.

당신은 당신의 파일

추가 귀하의 기능은 여전히 ​​잘못

유형 서명의 시작 부분에 {-# LANGUAGE NoMonomorphismRestriction #-}을 넣어 mxAdC x = go 0 x

를 사용

• 에 의한 유형의 오류를 수정할 수 있지만, 이제 typechecks.

  하스켈은 최상위 상수처럼 보이는 다형 함수 (= 앞에 매개 변수가 없음)를 금지합니다. 그래서 일반적으로 당신은 eta-reduce 수 없습니다 (foo x = bar x을 foo = bar으로 대체하십시오). https://stackoverflow.com/a/32496865/805266

Answer 3

기타 유형의 오류를 설명했다이 답변을 참조 - 전체 설명은 다소 깁니다. 보다 재미있는 실수를 살펴 봅시다.

| null ((x:xs)) = error "The list is empty" 

무엇이 잘못 되었습니까? x : xs은 null이 아닙니다. 첫 번째 요소가 x이기 때문에 가능하지 않을 수 있습니다! 당신이 여기서 뭘 의미하는 것은 그 다음 문제는이 카운트가 제로가 아닌 한 빨리, 당신이 완료 말한다

| count /= 0  = (mx, count) 

입니다

mxAdC ys 
    | null ys = error "mxAdC: the list is empty" 
    | otherwise = go 0 ys 
    where ... 

했다. 그래서 당신은 1을 넘지 않을 것입니다. 당신은 재귀에 기본 케이스가 필요하다는 것을 인식 했으므로, 당신은 하나를 넣으려고했으나, 그 마크를 놓쳤습니다. 당신이 필요로하는 기본 케이스는 빈리스트를 처리하는 것입니다

go count [] = ? 
go count (x:xs) 
    | x == mx   = go (count+1) xs 

뭔가 여전히하지만, go에서 누락되었습니다. x /= mx 일 때 무엇을하고 싶습니까?

go count [] = ? 
go count (x:xs) 
    | x == mx   = go (count+1) xs 
    | otherwise  = ? 

마지막 주요 문제는 당신이 go 함수 내에서 mx를 정의한다는 것입니다 : 당신은 (사용자가 입력하는 나는 물음표를 떠 났어요) 또 하나의 사례를 추가해야합니다. 이 때마다 매번 go 목록의 모든 부분이 전달 된 최대 값이 계산됩니다. 당신이하고 싶은 처리하는 두 개의 큰 효율성 문제가 여전히있다 mxAdC

mxAdc ys 
    | .... 
    where 
    go ... 
    mx = maximum ys 

---

에 mx을 정의합니다. 한 가지 문제점은 더 이상 누설 호출에서 accumulator의 계산을 강제하지 않아 공간 누수가 발생할 수 있다는 것입니다. 최대 값을 계산하기 위해 한 번하고 다시는 발생 횟수 계산이 쉽게 마지막 문제는 여전히 두 번 목록을 통과한다는 것입니다

go !count [] = ? 
go !count (x:xs) 
    | x == mx   = go (count+1) xs 
    | otherwise  = ? 

으로 BangPatterns 언어 확장을 사용하여 고정한다. 단 한번의 패스만으로도 가능합니다. 모든 세부 사항을 알려주지는 않겠지 만 기본 트릭은 go 함수를 변경하여 지금까지 본 것 중 가장 큰 요소와 본 횟수를 변경하는 것입니다. null 대신에 패턴 일치를 사용하여 나머지 부분을 mxAdC에 맞게 조정해야합니다.