2012-05-14 5 views
5

기능적 프로그래밍을 처음 접했기 때문에 기능적 접근 방식을 사용하여 해결하기가 다소 어려워 보입니다.이전 계산에 대한 정보를 계속 수행하십시오.

1에서 10.000과 같은 숫자 목록이 있고 최대 n까지 합계하는 목록의 항목을 가져 오려고한다고 가정 해 봅니다 (100이라고 가정). 따라서 합계가 100보다 커질 때까지 숫자를 얻을 수 있습니다.

명령형 프로그래밍에서는 각 상호 작용에서 변수를 유지하고 목적이 충족되면 중지 할 수 있기 때문에이 문제를 해결하는 것이 쉽지 않습니다.

그러나 함수 프로그래밍에서 어떻게 동일한 작업을 수행 할 수 있습니까? sum 함수는 완성 된리스트에 대해 연산을 수행하기 때문에 완성 된리스트가 아직 없기 때문에 어떻게 계산을 계속할 수 있습니까?

합 느리게 계산 된 경우, 그 뭔가를 작성할 수

  (1 to 10000).sum.takeWhile(_ < 100) 

PS : 어떤 대답을 이해할 수 있지만, 나는 이후, 합계 각 시간을 계산하지 않는 일을하고 싶습니다 분명히 명령형은 속도와 관련하여 훨씬 더 최적이 될 것입니다.

편집 :

나는 기능 재귀 함수에 필수적 루프 접근 방식을 "변환"수 있다는 것을 알고. 나는 기존 라이브러리 함수 중 하나가 내가 필요할 때마다 하나를 쓰지 않는 방법을 제공 할 수 있는지 찾는 것에 더 관심이있다.

+1

아마도 변수 누산기를 사용하는 것이 가장 쉽습니다. '{var sum = 0; (1 ~ 10000) takeWhile {i => sum + = i; 합 <100}}'. 여기에'var'을 가지는 것에는 아무런 문제가 없습니다; 표현식에'{}'이 있기 때문에 이스케이프 할 수 없습니다. –

+0

왜 "무언가가 필요할 때마다"함수를 작성하는 것이 당신이 무언가를 필요로 할 때마다 명령형 루프를 작성하는 것보다 자연스러운 것이라고 생각합니까? – Ben

답변

7

Stream을 사용하십시오.

scala> val ss = Stream.from(1).take(10000) 
ss: scala.collection.immutable.Stream[Int] = Stream(1, ?) 

scala> ss.scanLeft(0)(_ + _) 
res60: scala.collection.immutable.Stream[Int] = Stream(0, ?) 

scala> res60.takeWhile(_ < 100).last 
res61: Int = 91 

편집 :

얻기 구성 요소 중 하나를 매우 까다로운 없습니다. 이것은 당신이 그것을 할 수있는 방법은 다음과 같습니다

scala> ss.scanLeft((0, Vector.empty[Int])) { case ((sum, compo), cur) => (sum + cur, compo :+ cur) } 
res62: scala.collection.immutable.Stream[(Int, scala.collection.immutable.Vector[Int])] = Stream((0,Vector()), ?) 

scala> res62.takeWhile(_._1 < 100).last 
res63: (Int, scala.collection.immutable.Vector[Int]) = (91,Vector(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13)) 

튜플의 두 번째 부분은 원하는 결과입니다.

분명히 알 수 있듯이이 경우 벡터를 만드는 것은 낭비입니다. 대신 합계에 기여한 스트림의 마지막 번호 만 저장할 수 있습니다.

scala> ss.scanLeft(0)(_ + _).zipWithIndex 
res64: scala.collection.immutable.Stream[(Int, Int)] = Stream((0,0), ?) 

scala> res64.takeWhile(_._1 < 100).last._2 
res65: Int = 13 
+0

OP가 항목이 아니라 합계가 아닌지 질문했습니다. 이것은 조금 더 까다로울 것 같습니다. – ziggystar

+0

Ziggystar, 네 말이 맞아. 목록의 항목을 가져오고 싶습니다. 이 scanLeft는 몇 가지 문제를 해결하지만 100까지 합계 된 항목을 반환하지 않습니다. –

+0

ziggystar, Vinicius, 편집을 참조하십시오. – missingfaktor

1

내가 이렇게 할 방법은 재귀입니다. 각 통화에서 다음 번호를 추가하십시오. 기본 케이스는 합계가 100보다 큰 경우입니다.이 시점에서 스택 위로 돌아옵니다. 실제 재귀를 수행하는 도우미 함수가 필요하지만 큰 문제는 아닙니다.

1

"기능적"방법을 사용하는 것은 어렵지 않습니다.
재귀를 사용하여 변형 된 로컬 변수에서 상태를 유지 관리하는 대신 매개 변수와 반환 값으로 유지합니다.

그래서, 합계 최대 N입니다 목록의 가장 긴 처음 부분으로 돌아 가기 :

  1. 목록이 비어 있으면, 당신은 완료를; 빈 상태 (empty)의리스트를 돌려줍니다.
  2. 목록의 머리가 N보다 큰 경우 작업이 완료되었습니다. 빈 상태 (empty)의리스트를 돌려줍니다.
  3. 그렇지 않으면 H을 목록의 헤드라고합시다.
    우리가 지금 필요로하는 것은 합이 최대로 N - H 인 목록의 꼬리의 초기 부분입니다. 그러면 우리는 그 목록에 "cons"H을 할 수 있습니다.
    우리는 지금까지 사용한 것과 동일한 절차를 사용하여 재귀 적으로 계산할 수 있으므로 쉬운 단계입니다.

간단한 의사 솔루션 : 순서를 통해 하나의 패스를 필요로하는 모든 시퀀스 작업이이라고도처럼 주름이 우리의 감소 사용하여 구현 될 수있다

sum_to (n, ls) = if isEmpty ls or n < (head ls) 
       then Nil 
       else (head ls) :: sum_to (n - head ls, tail ls) 

sum_to(100, some_list) 
+0

내가 정말로 원하는 것을 반영하도록 내 질문을 편집했습니다. –

0

. 은 내가 함수형 프로그래밍에 사용 된 이후 자신이 자주 주름을 사용하여 찾을 수

하나의 가능한 방법 를 사용하여 초기 값으로 빈 수집 및 처리를 수집하고 새 값을 체크하는 경우를 감안할 때이 전략 에 따라 배 그래서 여기 홀수 그들의 합이 충분히 낮 으면 컬렉션에 값을 쓰지 않으면 아무것도하지 마십시오.

그 해결책은별로 효율적이지 않지만 다음을 강조하고 싶습니다. 지도 접이식 필터 우편 등은 함수형 프로그래밍에 익숙해지는 방법입니다. loping 구조 나 재귀 함수 대신 최대한 많이 사용하려면 코드가 더 선언적이고 기능적 일 것입니다. l

관련 문제