How to pass a type/tree in a function-CodePudding

I have these defined types

   type Name = string
   type Flow = int
   type River = R of Name * Flow * River list
   type Tributaries = River list

And i want to declare a function contains n r that returns a boolean value if n is contained in River or any of it's branches/Tributaries. and i've came up with this so far

let rec contains (n:Name)(r:River) =
    match r with
        |R(Name,_,_) when Name = n -> true 
        |R(_,_,Tr) -> contains n Tr
        |_ -> false

However F# cant recoginze Tr as Tr is a list and not of type river so i can't pass it in of course, how can i do this in a nice and clean way without declaring two seperate functions to help?

CodePudding user response：

Gus's answer fixes the specific issue and answers the question, but often things like this are slightly more elegant if work on a list of rivers (a 'forest' of trees) rather than a single one.

The solution is a little odd because the recursive step creates a new river to search in based on the tail of the tributaries of the input river, perfectly valid, but if feels a little odd.

first lets tidy up the types

type Name = string
type Flow = int
type Tributaries = River list
and River = R of Name * Flow * Tributaries

now we write something that feels harder than what you want to do, but is in fact (to me) intuitively easier to understand, i.e. you check the tail of the passed list AND you check the tributaries into the current river.

let rec containsTributaries (n: Name) (rs: River list) =
    match rs with
    | R (name, _, _) :: _ when name = n -> true
    | R (_, _, tribs) :: tail -> containsTributaries n tail || containsTributaries n tribs
    | _ -> false

then searching for a single river is trivial

let rec contains (n: Name) (river: River) =
    containsTributaries n [ river ]

(but basically this is the same answer as Gus's)

CodePudding user response：

The problem is Tr is a list and your function expect a River structure.

So, you would have to decompose the list in head and tail and check on both.

You can do that by changing the second match:

|R(_,_,Tr) -> contains n Tr

| R (name, f, x::xs) -> contains n x || contains n (R (name, f, xs))

Of course there are more efficient ways of doing this and you can use built in functions, but if you're learning this is the solution you want to come up in first place.