AList.partition

[fradav]

Similar to List.partition, adaptively.

A quick and dirt would be :

module AList =
    let partition<'a> (p: 'a -> bool) (l : clist<'a>) =
        let (left,right) = (clist<'a>[],clist<'a>[])
        let addRow (row: 'a) =
            match p row with
            | true  -> transact (fun () -> left.Add row)  
            | false -> transact (fun () -> right.Add row)
            |> ignore
        let removeRow (o: IndexList<'a>) (i : Index) =
            match p o.[i] with
            | true  -> transact (fun () -> left.Remove i)  
            | false -> transact (fun () -> right.Remove i)
            |> ignore
        let processDelta o (i : Index, e : ElementOperation<'a>) =
            match e with
            | Remove -> removeRow o i
            | Set(s) -> addRow s
            |> ignore
        l.AddCallback (fun o c -> c.ToList() 
                                      |> List.iter (processDelta o)) 
        |> ignore
        (left,right)

[fradav]

A proper way (but clearly an not optimized one) :

    let partition (predicate : 'T -> bool) (list: alist<'T>) =
        // TODO; Avoid reapplying the filter a second time
        if list.IsConstant then
            (constant (fun () -> list |> force |> IndexList.filter predicate),
             constant (fun () -> list |> force |> IndexList.filter (predicate >> not)))
        else
            match list.History with
            | Some history ->
                (ofReader (fun () -> history.NewReader(IndexList.trace, FilterReader.DeltaMapping (fun _ v -> predicate v))),
                 ofReader (fun () -> history.NewReader(IndexList.trace, FilterReader.DeltaMapping (fun _ v -> predicate v |> not))))
            | None -> 
                (ofReader (fun () -> FilterReader(list, fun _ v -> predicate v)),
                 ofReader (fun () -> FilterReader(list, fun _ v -> predicate v |> not)))

I don't see how to make a simple reader function which makes only one pass from the list to be read.

[krauthaufen]

An easier (just as inefficient) way would be

let partition (predicate : 'T -> bool) (list : alist<'a>) =
    AList.filter predicate list, AList.filter (predicate >> not) list

I'm currently thinking about that but I suspect there might not be a significantly more efficient way. Nonetheless it would be possible to cache predicate appropriately s.t. it doesn't get invoked twice on the same element.

I'll let you know once I concluded my experiments

[krauthaufen]

So here's my current best attempt which basically uses a shared IndexCache for two (slightly customized) FilterReaders. Since they share a mutable cache locking became necessary but that shouldn't really be a problem here.

I'm off for now and maybe I'll come up with something better. Or maybe someone else has a better idea...

[<Sealed>]
type PartitionReader<'a>(input : alist<'a>, predicate : IndexCache<'a, bool>, side : bool) =
    inherit AbstractReader<IndexListDelta<'a>>(IndexListDelta.empty)

    let reader = input.GetReader()

    static member DeltaMapping (side : bool, predicate : IndexCache<'a, bool>) =
        IndexListDelta.choose (fun i op ->
            match op with
            | Remove -> 
                match lock predicate (fun () -> predicate.Revoke(i)) with
                | Some v when v = side -> Some Remove
                | _ -> None
            | Set v -> 
                let o, n = lock predicate (fun () -> predicate.InvokeAndGetOld(i, v))
                match n = side with
                | true -> 
                    Some (Set v)
                | false -> 
                    match o with
                    | Some v when v = side -> Some Remove
                    | _ -> None
        )

    override x.Compute(token) =
        reader.GetChanges token |> IndexListDelta.choose (fun i op ->

            match op with
            | Remove -> 
                match lock predicate (fun () -> predicate.Revoke(i)) with
                | Some v when v = side -> Some Remove
                | _ -> None
            | Set v -> 
                let o, n = lock predicate (fun () -> predicate.InvokeAndGetOld(i, v))
                match n = side with
                | true -> 
                    Some (Set v)
                | false -> 
                    match o with
                    | Some v when v = side -> Some Remove
                    | _ -> None
        )

let partition (predicate : Index -> 'a -> bool) (l : alist<'a>) =
    if l.IsConstant then
        let t, f = AList.force(l).Content |> MapExt.partition predicate
        AList.ofIndexList (IndexList.ofMap t), AList.ofIndexList (IndexList.ofMap f)
    else
        let predicate = IndexCache predicate
        match l.History with
        | Some history ->
            AList.ofReader (fun () -> history.NewReader(IndexList.trace, PartitionReader.DeltaMapping(true, predicate))),
            AList.ofReader (fun () -> history.NewReader(IndexList.trace, PartitionReader.DeltaMapping(false, predicate)))
        | None ->
            AList.ofReader (fun () -> PartitionReader(l, predicate, true)),
            AList.ofReader (fun () -> PartitionReader(l, predicate, false))

[fradav]

Pardon my ignorance on the subject, but isn't an internal compiler memoization for the predicate already there, this making this cache somewhat redundant?

[krauthaufen]

Hey, I don't think there's any optmization done for these predicates because any kind of memoization introduced by the compiler would need information about when to evict caches (which it generally can't have)

So afaik. there's no such thing (unless of course I am wrong)

[fradav]

You're surely right, I just thought of trivial predicates for which memoization should be too much a waste of memory and cpu cycles to be enforced on a compiler level basis.