What am I doing wrong with Set.Fold F#

问题:

Colouring problem :

Hello, I'm trying to implement a bool function that returns true when a color can be extended to a country and false otherwise but I'm having trouble working with sets as we cannot pattern match them...

My code :

type Country = string;;
type Chart = Set<Country*Country>;;
type Colour = Set<Country>;;
type Colouring = Set<Colour>;;

(* This is how you tell that two countries are neghbours.  It requires a chart.*)
let areNeighbours ct1 ct2 chart =
  Set.contains (ct1,ct2) chart || Set.contains (ct2,ct1) chart;;
(* val areNeighbours :
  ct1:'a -> ct2:'a -> chart:Set<'a * 'a> -> bool when 'a : comparison
  *)

(* The colour col can be extended by the country ct when they are no neighbours
according to chart.*)

let canBeExtBy (col:Colouring) (ct:Country) (chart:Chart) = col |> Set.fold (fun x -> (if (areNeighbours x ct chart) then true else false))

What is expected : we need to check if ct is a neighbour of any country in the col (assuming there are countries in the col), according to the neighbourhood defined in the chart. So if

chart = set
    [("Andorra", "Benin"); ("Andorra", "Canada"); ("Andorra", "Denmark");
     ("Benin", "Canada"); ("Benin", "Denmark"); ("Canada", "Denmark");
     ("Estonia", "Canada"); ("Estonia", "Denmark"); ("Estonia", "Finland");
     ...]

And

col = set 
    ["Andorra"]

Then canBeExt should return false when when ct = "Benin" or "Canada" or "Denmark" etc... As Andorra share a border with those countries and thus they cannot be coloured in the same colour as Andora.

Obviously I have a type error in canBeExtBy as I'm trying to return a bool and it's expecting 'a:Colouring. I don't know how to implement it..

Thanks for your help !

回答1:

What about this?

type Country      = string
type Neighbours   = Set<Country*Country>
type SharesColour = Set<Country>

let areNeighbours (ns : Neighbours) (ct1 : Country) (ct2 : Country) : bool =
  Set.contains (ct1,ct2) ns || Set.contains (ct2,ct1) ns

let canShareColour (ns : Neighbours) (ct : Country) (s : SharesColour) : bool =
  s |> Seq.exists (areNeighbours ns ct) |> not

let neighbours : Neighbours = 
  set [| 
    ("Andorra", "Benin")  ; ("Andorra", "Canada") ; ("Andorra", "Denmark");
    ("Benin"  , "Canada") ; ("Benin"  , "Denmark"); ("Canada" , "Denmark");
    ("Estonia", "Canada") ; ("Estonia", "Denmark"); ("Estonia", "Finland");
  |]

let sharesColour : SharesColour =
  set [|
    "Andorra"
  |]

[<EntryPoint>]
let main argv =
  printfn "%A" <| canShareColour neighbours "Estonia" sharesColour
  printfn "%A" <| canShareColour neighbours "Benin"   sharesColour
  0

Changed the names to something that made more sense to me. You might not agree.

回答2:

To check that no element in a collection satisfies a given condition: that's not a job for fold, but, with appropriate negation, for exists or forall. Either of

    let fornone f = Set.forall (f >> not)
    let doesnotexist f = Set.exists f >> not

will do, as shown in the answer of FuleSnabel. However, it is certainly possible to build these functions from a fold, albeit nobody would do that except as an illustration of currying, function composition and pointfree style.

    let fornone f = Set.fold (fun s -> f >> not >> (&&) s) true
    let doesnotexist f = Set.fold (fun s -> f >> (||) s) false >> not