하스켈에서 명시 적 재귀

Question

작업 : 형식 minimum_recursive :: (a -> a -> Bool) -> [a] -> a 형식의 함수를 작성하려고합니다. 첫 번째 매개 변수의 경우 두 개의 매개 변수를 사용하는 less이라는 함수를 허용하고 첫 번째 매개 변수가 두 번째 매개 변수보다 작 으면 True를 반환하고 그렇지 않으면 False를 반환합니다. minimum_recursive은 두 번째 매개 변수로 목록을 받아들입니다. 명시 적 재귀를 사용하면 minimum_recursive은 입력 목록 [a]에서 가장 작은 값을 결정해야합니다.

내 생각 : 나는 누산기를 허용하는 도우미 함수에 실제 재귀를 넣으려고했다. 첫 번째 항목을 누적기로 사용하여 도우미 함수를 호출합니다. 내가 지금까지 무엇을 가지고

: 지금까지 나는 다음과 같습니다

-- function as first parameter to min' 
-- accepts two params, returns True if 
-- first must come before second in sorted 
-- order 
less :: Ord a => a -> a -> Bool 
less a b = a < b 

-- Subpart B 
minimum_recursive :: (a -> a -> Bool) -> [a] -> a 
minimum_recursive func list = minimum_recursive_h func list [] 

심지어 minimum_recursive_h을 쓰기 시작하는 방법을 알아내는 문제을 데.

참고 : 나는이 작업을 수행하는 더 쉬운 방법이 있음을 알고 있지만 위에 지정된대로 그것에 대해 알아야합니다.

Answer 1

이처럼 할 수있는 재귀 문제를 해결하기

minimum_recursive _ [] = error "no minimum of empty list" 
minimum_recursive f (x:xs) = helper f x xs 
    where 
     helper _ m [] = m 
     helper f m (x:xs) 
      | f m x = helper f m xs 
      | otherwise = helper f x xs 

Answer 2

목록에서 가장 작은 원소를 원한다면 현재 매개 변수로 가지고있는 가장 작은 원소를 함수에 추가하십시오. 빈 목록에 작은 ellement 없기 때문에

minimum_recursive :: (a -> a -> Bool) -> a -> [a] -> a 
minimum_recursive f min [] = min 
minimum_recursive f min (x:xs) | f min x = minimum_recursive f min xs 
           | otherwise = minimum_recursive f x xs 

는 또한 Maybe a에 a에서이 전화 기능의 유형을 변경해야합니다. Here some help about Maybe

추가 매개 변수없이이 작업을 수행하려는 경우 가장 작은 항목을 목록 엉덩이의 처음에 잘 저장할 수 있습니다. 이 경우에 사용하는 것이 중요합니다.

이렇게하면 최소값을 찾을 수 있습니다. 전체 기능 프로그래밍의 아름다움을보십시오. 그러나 빈 목록에 대해서는 작동하지 않습니다.

simplefold :: [a] -> a 
simplefold (x:xs) = foldl min x xs 

그러나 목록이 비어 있는지 확인하고이 경우 Nothing을 반환하는 함수에이 함수를 포함시킬 수 있습니다. 어큐뮬레이터로,

minimum_recursive _ [] = error "no minimum of empty list" 
minimum_recursive _ [x] = x 
minimum_recursive f (x:xs) = let m = minimum_recursive f xs 
          in if f x m then x else m 

을 또는 :

betterfold :: [a] -> Maybe a 
betterfold [] = Nothing 
beterfold l = Just (simplefold l) 

Answer 3

고전적인 방법으로는 다음과 같다

1. 마지막 문제를 제외하고는 거의 문제를 해결했다고 가정 해 봅시다. 어서.
2. 마지막 단계를 제외한 모든 것에 대한 해가 주어진 경우 최종 단계에서 생성 된 해를 계산하는 코드를 작성하십시오.
3. 기본 케이스를 작성하십시오.목록의 경우

이이 패턴으로 변환 :

1. 자료의 경우 :이 솔루션은 [] 무엇을해야 하는가? (어떤 것이 든, minimum_recursive 함수의 경우 이것은 오류입니다).
2. 비어 있지 않은 목록 x:xs의 경우 이미 almostTheResult = minimum_recursive f xs이 있다고 가정합니다. 어떻게 주어진 minimum_recursive (x:xs) 계산합니까?

나는 당신에게 큰 힌트를 줄 것이다 : 당신의 minimum_recursive이 foldr의 관점에서 구현 될 수 있으며,이 기능을 :

minBy :: (a -> a -> Bool) -> a -> a -> a 
minBy pred x y = if pred x y then x else y 

foldr 기능은 제가 위에서 설명하고있어 정확히 않습니다. foldr의 첫 번째 인수는 목록 머리와 꼬리 부분 솔루션을 주어진 최종 솔루션을 계산하는 함수이며 두 번째 인수는 결과 기본 경우입니다.