Quicksort في سؤال S# - بناء الجملة

Question

لدي وظيفة بسيطة f# sort Quick Function على النحو التالي:

let rec qsort(xs:List<int>) =

let smaller = xs |> List.filter(fun e -> e < xs.Head)
let larger = xs |> List.filter(fun e -> e > xs.Head)
match xs with
| [] -> []
| _ -> qsort(smaller)@[xs.Head]@qsort(larger)

هل هناك طريقة في F# لكتابتها أكثر مثل Haskell:

qsort       :: [Int] -> [Int]
qsort []     = []
qsort (x:xs) =
qsort smaller ++ [x] ++ qsort larger
where
  smaller = [a | a <- xs, a <= x]
  larger  = [b | b <- xs, b >= x]

أعلم أن خوارزمية F# تفتقد <= و> =. السؤال هو أكثر حول بناء الجملة/القراءة.

شكرًا.

Answer 1

تريد أن يكون شرط المباراة الثاني الخاص بك x :: xs, ، واستخدام مشغل @ (إلحاق) حيث يستخدم مثال Haskell ++:

let rec qsort xs =
  match xs with
  | [] -> []
  | x :: xs ->
      let smaller = qsort (xs |> List.filter(fun e -> e <= x))
      let larger  = qsort (xs |> List.filter(fun e -> e >  x))
      smaller @ [x] @ larger

إنه ليس هو نفس تعريف Haskell حسب بناء الجملة ، ولكن نأمل أن يكون متشابهًا بما يكفي بالنسبة لك!

Answer 2

هذه هي الطريقة الأكثر "Haskellian" التي يمكنني التفكير فيها ، والشيء الوحيد المفقود هو أن تكون قادرًا على الإعلان عن أصغر/أكبر كـ "جملة":

let rec qsort:int list -> int list = function
    | [] -> []
    | x::xs -> let smaller = [for a in xs do if a<=x then yield a]
               let larger =  [for b in xs do if b>x then yield b]
               qsort smaller @ [x] @ qsort larger

أعلم أنه ليس جزءًا من سؤالك ، لكنني سأستخدمه List.partition لتقسيم القائمة في أصغر/أكبر في تمريرة واحدة:

let rec qsort = function
    | [] -> []
    | x::xs -> let smaller,larger = List.partition (fun y -> y<=x) xs
               qsort smaller @ [x] @ qsort larger

Answer 3

... أو يمكنك صنع ذيل qsort عودية باستخدام CPS:

let qSort lst = 
   let rec qs l cont = 
       match l with
       | []      -> cont []
       | (x::xs) -> qs (List.filter (fun e -> e <= x) xs) (fun smaller ->
                    qs (List.filter (fun e -> e >  x) xs) (fun larger  ->
                        smaller @ (x :: larger) |> cont))
   qs lst id

Answer 4

يبدو أن هذا موجز قدر الإمكان (الجمع بين الأفكار من الإجابات الأخرى ، واستخدام الكاري للمشغلين):

let rec qsort = function
| [] -> []
| (x:int) :: xs ->
    let smaller = List.filter ((>=) x) xs
    let larger  = List.filter ((<) x) xs
    qsort smaller @ [x] @ qsort larger

Answer 5

Haskell 'Where' Syntax ، والذي يتيح لك استخدام اسم وظيفة قبل تعريفها ، ونوع من الخرائط إلى f# "دع REC ... و"

let qsort xs =
    let rec sort xs = 
        match ls with
        |[] -> ....
        |h::t -> (smaller t) @ h @ (larger t)

    and smaller ls =    //the 'and' lets you define the 
                        //  function after where it is used, 
                        //  like with 'where' in haskell
         ... define smaller in terms of sort
    and larger ls =
         ... same

    sort xs

Answer 6

let  rec QuickSort l =
        match   l with  
        |  []  ->  []
        |   _   ->  QuickSort([for e in l do if e < (List.head l) then yield e]) @[(List.head l)]@ QuickSort([for e in l do if e > (List.head l) then yield e])

Answer 7

لا تنس أن القائمة لها طريقة قسم ، لذلك

let rec quicksort ls =
    match ls with
    | [] -> []
    | h :: t -> let fore, aft = List.partition (fun i -> i < h) t
                (quicksort fore) @ (h :: quicksort aft)

Answer 8

لقد أجريت بعض التحليلات لفرز الخوارزميات في F# قبل بضع سنوات بأسلوب ضروري للغاية ؛ كنت أحاول التغلب على تنفيذ أسهم .NET ، وتمكنت من القيام بذلك هنا. ذهبت لإجراء الرد التالي على نفسي اليوم ، لكن FPISH لن تسمح لي بإنشاء حساب. أرغ! يجب أن أجعل منصبي في مكان ما ، وإليك جيد مثل أي مكان ، لول ...

أثناء قراءة "تعلمك لك هاسكل من أجل الخير العظيم" ، قام المؤلف بإعداد مثال لتنفيذ QuickSort. كان الوصف واضحًا تمامًا ، وحتى قبل أن أصل إلى رمز العينة ، ظهر حل متكرر أنيق (في هاسكل) في رأسي. أعتقد أنه لم يكن لدي أبدًا شعور بديهي لمدى قيامه بسرعة ، لأن الحل التافلي سهل للغاية ، إن لم يكن فعالًا للغاية.

ها هي روايتي في F#:

let rec quicksort = function
    | [] -> []
    | pivot :: xs ->
        (left pivot xs) @ pivot :: (right pivot xs)
and left pivot xs = quicksort [ for x in xs do if x <= pivot then yield x ]
and right pivot xs = quicksort [ for x in xs do if x > pivot then yield x ]

و ، المكافئ هاسكل (أحب هذا ... نظيف!):

quicksort :: Ord a => [a] -> [a]
quicksort [] = []
quicksort (pivot : xs) =
    left ++ pivot : right
    where
        left = quicksort [ x | x <- xs, x <= pivot ]
        right = quicksort [ x | x <- xs, x > pivot ]

بالنسبة للابتسامات ، إليك إصدار F# آخر (معظمه من العلم) الذي يبلغ حوالي 2x سرعة الإصدار التافهة. لم يزعج ذلك الوقت ضد مشاركتي الأصلية ، لذلك ، لذلك لا توجد فكرة عن كيفية تداخل الإصدار القابل للتغيير في OP الخاص بي على fpish.net (fshub) منذ بضع سنوات ...

let rec quicksort' xs =
    let rec aux pivot left right = function
        | [] -> (quicksort' left) @ pivot :: (quicksort' right)
        | x :: xs ->
            if x <= pivot then
                aux pivot (x :: left) right xs
            else
                aux pivot left (x::right) xs
    match xs with
    | [] -> []
    | x :: xs -> aux x [] [] xs