꼬리 재귀

Question

내가 꼬리 재귀를 사용하여 주어진 요소의 인덱스를 찾기 위해 함수를 작성하려고를 사용하여 주어진 요소의 인덱스를 찾기. 목록 110까지의 숫자를 포함라고, 나는 5 검색하고, 출력이 4을해야 할 수 있습니다. 내가 겪고있는 문제는 꼬리 재귀를 사용하여 '계산'하는 것입니다. 그러나,이 경우 재귀 호출 수를 maunally 'count'해야하는지 잘 모르겠습니다. 나는 특정 위치에 요소를 반환하기 때문에 도움이되지 않는 !!을 사용해 보았습니다. 특정 요소 (정확한 반대 위치)의 위치를 ​​반환하는 함수가 필요합니다.

는 지금은 시간이 일을 알아 내려고 노력하고있다.

코드 :

whatIndex a [] = error "cannot search empty list" 
    whatIndex a (x:xs) = foo a as 
    where 
     foo m [] = error "empty list" 
     foo m (y:ys) = if m==y then --get index of y 
         else foo m ys 

참고 : 나는 라이브러리 함수를

Answer 1

도우미 기능을 사용하지 않고이를 구현하기 위해 노력하고 카운트에 대한 추가 매개 변수를 필요로한다.

whatIndex a as = foo as 0 
    where 
    foo [] _ = error "empty list" 
    foo (y:ys) c 
     | a == y = c 
     | otherwise = foo ys (c+1) 

BTW, 그것은 오류를 사용하는 대신이 기능에게 Maybe 반환 유형을주고 더 나은 형태입니다. 그것은 좋은 이유 때문에 elemIndex이 작동하는 방법입니다. 이

whatIndex a as = foo as 0 
    where 
    foo [] _ = Nothing 
    foo (y:ys) c 
     | a == y = Just c 
     | otherwise = foo ys (c+1) 

Answer 2

주 같을 것이다 : 나는 라이브러리 함수

이것은 일반적으로 좋은 생각이 아니다를 사용하지 않고이를 구현하기 위해 노력하고 있습니다. 더 나은 운동은 다음과 같습니다.

1. 라이브러리 함수를 사용하여 구현하는 방법을 설명합니다.
2. 1 단계에서 사용한 라이브러리 함수를 사용자가 직접 구현하는 방법을 설명합니다.

당신은 세 가지 핵심 기술을 배우고이 방법 :가 유용 할 때의 표준 라이브러리 함수 및 예제은 무엇

• .
• 는 라이브러리에있는 것과 같은 기본 기능을 작성하는 방법을 작은 조각
• 에 문제를 휴식하는 방법. 이 경우

, 그러나, 당신의 whatIndex는 elemIndex in Data.List로 더 많거나 적은 동일한 기능이므로, 문제는이 라이브러리 함수의 자신의 버전을 쓰기로 줄일 수 있습니다.

여기에 트릭

당신이 목록을 아래로 재귀하는 동안 카운터를 증가 할 것입니다. 꼬리 재귀 함수를 작성하는 표준 기술은 인 누적 매개 변수라고합니다.그것은 다음과 같이 작동

1. 당신은의 "프런트 엔드"기능에 비해 여분의 정보를 추적하기 위해 추가 매개 변수 (또는 그 이상)을 취하는 보조 함수를 작성합니다.
2. 그런 다음 "실제"기능을 보조 기능 호출로 정의합니다.

그래서 elemIndex위한 보조 기능 (현재 요소 지수 집적 매개 변수 i 포함)이 다음과 같을 것이다 :

-- I'll leave the blanks for you to fill. 
elemIndex' i x []  = ... 
elemIndex' i x (x':xs) = ... 

그러자 "드라이버"기능이있다 :

여기에 심각한 문제가 있습니다. 언급해야 할 내용은 다음과 같습니다. 하스켈에서이 기능을 잘 수행하는 것은 까다로운 도구입니다.. 때문에 꼬리 재귀, 하스켈에서 너무 많은 엄격한 (비 지연) 함수형 언어에 유용한 트릭이지만,하지 :

1. 하스켈에서 꼬리 재귀 함수는 여전히 스택을 날려 버릴 수
2. non-tail-recursive 함수는 상수 공간에서 실행될 수 있습니다.

This older answer of mine은 두 번째 지점의 예를 보여줍니다.

elemIndex x xs = elemIndex' x (zip xs [0..]) 

elemIndex' x pairs = snd (find (\(x', i) -> x == x') pairs) 

-- | Combine two lists by pairing together their first elements, their second 
-- elements, etc., until one of the lists runs out. 
-- 
-- EXERCISE: write this function on your own! 
zip :: [a] -> [b] -> [(a, b)] 
zip xs ys = ... 

-- | Return the first element x of xs such that pred x == True. Returns Nothing if 
-- there isn't one, Just x if there is one. 
-- 
-- EXERCISE: write this function on your own! 
find :: (a -> Bool) -> [a] -> Maybe a 
find pred xs = ...