기능적 : 정수 목록 1..N

StackOverflow https://stackoverflow.com/questions/828765

문제

이것은 숙제가 아닙니다. 나는 스스로 표준 ML을 배우고 있습니다. 나는 약간의 계획도 알고 있으므로이 질문은 어느 언어로든 대답 할 수 있어야합니다.

내 자체 부과 할당은 정수 목록을 1에서 n까지 구성하는 함수를 작성하는 것입니다. 예를 들어, 목록 (7)은 [1,2,3,4,5,6,7]를 반환해야합니다. O (n) 솔루션이 이상적입니다.

선형 시간에 리버스 (IE, [n, n-1, .., 1])로 목록을 쉽게 구성 할 수 있습니다.

fun list 1 = 1::nil
|   list n = n::list(n-1);

앞으로 목록을 구성하려는 나의 시도는 Append 작업이 선형이기 때문에 O (n^2)입니다.

fun list 1 = 1::nil
|   list n = list(n-1) @ n::nil;

다음 시도는 끝에서 앞쪽으로 (오른쪽에서 왼쪽으로) 목록을 작성하여 nil로 시작하여 n을 앞쪽에 부착하고 1으로 뒤집습니다. 그러나 전혀 작동하지 않았습니다.

fun list n = (if n = 1
              then 1
              else list(n-1) :: n) :: nil;

재귀에 사용될 미지급 목록을 작성하는 도우미 기능이 필요하다고 생각합니다.

도움이 되었습니까?

해결책

사용 기본 라이브러리,

fun list n = List.tabulate (n, fn x => x + 1)

간단한 축적기로

val list =
    let fun list' k 0 = k
          | list' k n = list' (n::k) (n-1)
    in list' nil end

이것은 꼬리 끝에서 시작하는 목록을 작성합니다. 감소를 생각하면

   list 5
=> list' nil 5
=> list' (5::nil) 4
=> list' (4::5::nil) 3
=> list' (3::4::5::nil) 2
=> list' (2::3::4::5::nil) 1
=> list' (1::2::3::4::5::nil) 0
=> [1, 2, 3, 4, 5]

대안 적으로,

재귀에 사용될 미지급 목록을 작성하는 도우미 기능이 필요하다고 생각합니다.

종료되지 않은 목록의 표현은 목록을 취하고 목록을 반환하는 함수입니다. 10::_, 당신은 사용할 수 있습니다 fn x => 10::x.

fun list n =
    let fun list' m k = if m > n then k nil else
                        list' (m+1) (fn x => k (m::x))
    in list' 1 (fn x => x) end

다시 한번, 감축을 생각하면

   list 5
=> list' 1 (fn x => x)
=> list' 2 (fn x => (fn x => x) (1::x))
=> list' 3 (fn x => (fn x => (fn x => x) (1::x)) (2::x))
=> list' 4 (fn x => (fn x => (fn x => (fn x => x) (1::x)) (2::x)) (3::x))
=> list' 5 (fn x => (fn x => (fn x => (fn x => (fn x => x) (1::x)) (2::x)) (3::x)) (4::x))
=> list' 6 (fn x => (fn x => (fn x => (fn x => (fn x => (fn x => x) (1::x)) (2::x)) (3::x)) (4::x)) (5::x))
=> (fn x => (fn x => (fn x => (fn x => (fn x => (fn x => x) (1::x)) (2::x)) (3::x)) (4::x)) (5::x)) nil
=> (fn x => (fn x => (fn x => (fn x => (fn x => x) (1::x)) (2::x)) (3::x)) (4::x)) (5::nil)
=> (fn x => (fn x => (fn x => (fn x => x) (1::x)) (2::x)) (3::x)) (4::5::nil)
=> (fn x => (fn x => (fn x => x) (1::x)) (2::x)) (3::4::5::nil)
=> (fn x => (fn x => x) (1::x)) (2::3::4::5::nil)
=> (fn x => x) (1::2::3::4::5::nil)
=> [1, 2, 3, 4, 5]

이 경우, 알고리즘은 일반적인 데이터 구조가 축합기에 충분하지 않도록 구조화 될 수 있지만 축적기로 연속을 사용하는 것은 간과해서는 안되는 매우 강력하고 유용한 기술입니다.

다른 팁

전형적인 방법 중 하나는 역 순서로 구축 한 다음 반대로하는 것입니다. 그것은 O (n)의 두 배입니다. 물론 O (n)과 마찬가지입니다.

다음은 해결책입니다.

fun list n =
  let
    fun f 1 m = m::nil
    |   f n m = m::f (n-1) (m+1)
  in
    f n 1
  end;

다음은 헬퍼 기능과 꼬리 재수 전환 축적기를 사용하는 버전입니다.

fun list n =
  let
    fun aux i acc = 
      if i > 0
      then aux (i-1) (i::acc)
      else acc
  in
    aux n nil
  end;

이와 같은 목록 문제를 사용하면 더 일반적인 문제를 해결하기가 더 쉽습니다.

정수가 포함 된 목록을 어떻게 작성합니까? 나 그렇게 n <= i <= m, 순서대로?

솔루션에는 기본 사례와 유도 단계가 있습니다.

  • 만약에 n> m, 목록은 비어 있습니다.

  • 만약에 n <= m, 해결책은 쓰는 것입니다 N 문제에 대한 해결책이 뒤 따릅니다 n+1 <= i <= m.

이보기는 빠르게 간결하고 간결한 ML 코드 (테스트)로 이어집니다.

fun range n m = if n > m then [] else n :: range (n+1) m
fun list n = range 1 n

(define (iota n)
  (let f ((i n)(a '())
    (if (zero? i)
        (reverse a)
        (f (- i 1) (cons i a)))))
라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top