2

我有一个非常琐碎的任务,但我不知道如何使解决方案更漂亮。
目标是List根据是否通过谓词来获取并返回结果。结果应该分组。这是一个简化的示例:

谓词:isEven
Inp : [2; 4; 3; 7; 6; 10; 4; 5]
Out: [[^^^^]......[^^^^^^^^]..]

这是我到目前为止的代码:

let f p ls =
    List.foldBack
        (fun el (xs, ys) -> if p el then (el::xs, ys) else ([], xs::ys))
        ls ([], [])
    |> List.Cons // (1)
    |> List.filter (not << List.isEmpty) // (2)

let even x = x % 2 = 0

let ret =
    [2; 4; 3; 7; 6; 10; 4; 5]
    |> f even
// expected [[2; 4]; [6; 10; 4]]

这段代码似乎不太可读。另外,我不喜欢第 (1) 和 (2) 行。有没有更好的解决方案?

4

6 回答 6

4

这是我的看法。你首先需要一些辅助函数:

// active pattern to choose between even and odd intengers
let (|Even|Odd|) x = if (x % 2) = 0 then Even x else Odd x

// fold function to generate a state tupple of current values and accumulated values
let folder (current, result) x =
    match x, current with
    | Even x, _ -> x::current, result // even members a added to current list
    | Odd x, [] -> current, result    // odd members are ignored when current is empty
    | Odd x, _ -> [], current::result // odd members starts a new current

// test on data
[2; 4; 3; 7; 6; 10; 4; 5]
    |> List.rev                             // reverse list since numbers are added to start of current
    |> List.fold folder ([], [])            // perform fold over list
    |> function | [],x -> x | y,x -> y::x   // check that current is List.empty, otherwise add to result
于 2012-09-30T21:54:08.743 回答
2

这个怎么样?

let folder p l = function
    | h::t when p(l) -> (l::h)::t
    | []::_ as a -> a
    | _ as a -> []::a

let f p ls =
    ls
    |> List.rev
    |> List.fold (fun a l -> folder p l a) [[]]
    |> List.filter ((<>) [])

至少该文件夹非常清晰有效,但是您通过列表反转为此付出了代价。

于 2012-09-30T03:47:47.887 回答
0

这是一个基于递归的递归解决方案List.filter

let rec _f p ls =
    match ls with
    |h::t -> if p(h) then 
                 match  f p t with
                 |rh::rt -> (h::rh)::rt
                 |[] -> (h::[])::[]
             else []::f p t
    |[] -> [[]]

let  f p ls = _f p ls |> List.filter (fun t -> t <> [])

不过,必须在最后进行过滤似乎并不优雅。

于 2012-09-30T00:26:21.270 回答
0

我想不出一种使用高阶函数优雅地做到这一点的方法,但这里有一个使用列表理解的解决方案。我认为阅读起来相当简单。

let f p ls = 
  let rec loop xs = 
    [ match xs with 
      | [] -> ()
      | x::xs when p x -> 
        let group, rest = collectGroup [x] xs
        yield group
        yield! loop rest
      | _::xs -> yield! loop xs ]
  and collectGroup acc = function
    | x::xs when p x -> collectGroup (x::acc) xs
    | xs -> List.rev acc, xs
  loop ls
于 2012-09-30T02:57:24.260 回答
0

随着列表反转,我想去#seq而不是列表。

此版本在内部使用突变(喘气!)以提高效率,但也可能会因 seq 的开销而慢一些。我认为它是相当可读的。

let f p (ls) = seq {
    let l = System.Collections.Generic.List<'a>()
    for el in ls do
      if p el then 
        l.Add el
      else 
        if l.Count > 0 then yield l |> List.ofSeq
        l.Clear()
    if l.Count > 0 then yield l |> List.ofSeq
   }
于 2012-10-01T14:02:11.863 回答
0

干得好。这个功能也应该有相当不错的性能。

let groupedFilter (predicate : 'T -> bool) (list : 'T list) =
    (([], []), list)
    ||> List.fold (fun (currentGroup, finishedGroups) el ->
        if predicate el then
            (el :: currentGroup), finishedGroups
        else
            match currentGroup with
            | [] ->
                [], finishedGroups
            | _ ->
                // This is the first non-matching element
                // following a matching element.
                // Finish processing the previous group then
                // add it to the finished groups list.
                [], ((List.rev currentGroup) :: finishedGroups))
    // Need to do a little clean-up after the fold.
    |> fun (currentGroup, finishedGroups) ->
        // If the current group is non-empty, finish it
        // and add it to the list of finished groups.
        let finishedGroups =
            match currentGroup with
            | [] -> finishedGroups
            | _ ->
                (List.rev currentGroup) :: finishedGroups

        // Reverse the finished groups list so the grouped
        // elements will be in their original order.
        List.rev finishedGroups;;
于 2012-09-30T03:33:11.447 回答