하스켈이 목록에서 가장 큰 숫자를 삭제합니다.

Question

목록에서 가장 큰 요소를 찾아 목록을 반환하는 재귀 함수를 만드는 방법을 알아 내려고하고 있습니다. 이것은 내가 지금까지 가지고 있지만 문제는 내가 그것을 실행할 때마다 x에 할당 된 값이없는 목록을 반환한다는 것입니다.

deleteMax :: (Ord a) => [a] -> [a] 
deleteMax [] = [] 
deleteMax [x] = [] 
deleteMax (x:y:xs) 
    |x == y = y: deleteMax xs 
    |x >= y = y: deleteMax xs 
    |x < y = x: deleteMax xs 

Answer 1

이

그래서 당신이 초보자와 같은이 다음에 "어떻게 내가 목록에서 가장 큰 요소를 찾을 수 있습니까"의 간단한 솔루션을 원하는 답하지 않습니다 "어떻게 할 목록에서 가장 큰 요소를 제거하십시오 ". 이것은 그 대답이 아니지만 긴 코멘트를 피하면서 나에게 당신이 3 개월 만에 돌아올 것을주는 동안 나입니다.

게으른 방법

하나의 솔루션, @의 n.m. 그리고 나는 논평에 대해 스파링을하고 있었고, 매듭 (Google 용어)을 묶는 것이 었습니다. 이 방법에서는 목록에 대해 하나의 논리 전달 만 필요합니다. 이 경우 기본적으로 결과 목록을 구성하는 패스를 숨기는 트릭입니다.

아이디어를 얻으려면 목록을 통과하는 동안 1의 작업을 모두 수행해야합니다. 최대 요소를 계산하고 2를 계산합니다. 최대 요소와 비교하고 목록을 구성합니다. 이 모나드를 필요로 여기에 아무것도하지만 상태 모나드의 일환으로 볼 수있는 가장 쉬운 될 수 있습니다

deleteMaxState :: (Ord a) => [a] -> [a] 
deleteMaxState []  = [] 

먼저 우리는 우리가 후보 '최대'그래서 기본 경우를 처리 (x) 우리의 재귀 작동 . 두 값들이 ​​먼저 loopwe 트랙

deleteMaxState xs@(fstElem:_) = 
    let (r,(m,_)) = runState (go xs) (fstElem, notMax m) 
     notMax mx v = if (mx > v) then (v:) else id 
     go [] = return [] 
     go (x:xs) = 
      do (curr,f) <- get 
       when (x > curr) (put (x,f)) 
       f x <$> go xs 
    in r 

, curr는리스트의 탐색에 우리의 시점으로 큰 관측 값이다. 두 번째 값인 f은 트릭입니다. 이후에 계산 된 에 제공된 최대 값을 포함하는 함수입니다 (통과 기능 포함).

마법은 모두 여기에 있습니다 : 결과 상태 (m,_)의

(r,(m,_)) = runState (go xs) (fstElem, m) 

왼쪽 요소는 우리의 실행 최대이었다. 순회가 끝나면 그 값을 사용합니다. 오른쪽 요소 (fstElem, m)이되어 전체 목록의 최대 값을 나타냅니다.

f을 사용하여 목록의 일부를 채우는 썽크를 만들거나 우리의 목록을 평가되지 않은 cons 계산의 무리로 구성 할 수 있습니다.

deleteMaxState xs@(fstElem:_) = 
    let (r,(m,_)) = runState (go xs) (fstElem, m) 
     go [] = return [] 
     go (x:xs) = 
      do (curr,theMax) <- get 
       when (x > curr) (put (x,theMax)) 
       ((if x >= theMax then Nothing else Just x) :) <$> go xs 
    in catMaybes r 

이제 우리는하지 단지 평가되지 않은 세트로 꽤 명시 적으로 두 번째 패스를 볼 수 있습니다 IOTA 간단, 우리는 고차 기능 f을 제거 할 수 있습니다 단지 (테스트되지 않은) 번호를 가지고이 일을 만들기

"최대 계산과 관련된 일부 계산"의 결과가 아니라 catMaybes을 통한 실제 전달입니다.

매듭의 묶음은 프로그래머가 논리적 순회를 작성할 수있게 해줍니다. 이것은 list 요소의 생성자마다 하나의 패턴 일치 및 재귀 호출 만 필요하므로 평가 순서에 대한 추리를 희생 시키므로 유용 할 수 있습니다.