let rec common a b =
match isolate(a) b with
| (x::xs,isolate(b)) ->
if memberof(b x) then [x,common(xs b)]
else common(xs b)
Here is what I have right now, but I've been trying many different things. The memberof() takes a float list and a float and returns true if the float is a member of the float list. The memberof() function works. I can't figure out how to return the new list.
I also have an isolate() function which will take a list and remove any duplicate floats within the list. This seem like it may be helpful.
edit: I'm trying to figure out how to return my new list when xs = []. In this thread the answer is right until common which does not return the common members in a list but rather concatenated list containing all elements.
Example I would like common to produce the result:
[1.0;2.0;3.0;4.0;5.0] [4.0;3.0;9.0] -> [3.0;4.0]
Rather than 'common' producing:
[1.0;2.0;3.0;4.0;5.0] [4.0;3.0;9.0] -> [1.0;2.0;3.0;4.0;5.0;9.0]
How can I solve this problem using recursion?
Building upon the examples I gave as an answer to your earlier question.
Note: This is basically the same as the answer by TheInnerLight, I just used the format mentioned in the earlier questions and gave examples of all of the needed functions.
Since you appear to not be using this format I will walk through the steps I used to make the function common.
Start with
let funXYZ list =
let rec funXYZInner list acc =
match list with
| head :: tail ->
let acc = (somefunc head) :: acc
funXYZInner tail acc
| [] -> acc
funXYZInner list []
and name the function common
let common list =
let rec commonInner list acc =
match list with
| head :: tail ->
let acc = (somefunc head) :: acc
commonInner tail acc
| [] -> acc
commonInner list []
Common needs two input list and one output list.
First we will set the signature then then pass both list to commonInner.
At this point I have not decided how to handle the two list I know that I need them both to do the transformation function.
Since the output will come from the accumulator and be a list, we initialize the accumulator with an empty list in commonInner a b []
let common (a : 'a list) (b : 'a list) : 'a list =
let rec commonInner a b acc =
match list with
| head :: tail ->
let acc = (somefunc head) :: acc
commonInner tail acc
| [] -> acc
commonInner a b []
Now we can decide how to transform the two lists into one list with items common to both. Since the final list will not have duplicates, lets transform each list individually into list of unique items using isolate.
let common (a : 'a list) (b : 'a list) : 'a list =
let aUnique = isolate a
let bUnique = isolate b
let rec commonInner a b acc =
match list with
| head :: tail ->
let acc = (somefunc head) :: acc
commonInner tail acc
| [] -> acc
commonInner aUnique bUnique []
At this point when we reach the match statement we have the two list. We only need to compare each item in one list against the other list and when they are the same do something with the item.
With functional programming one has to be aware that list are immutable and use that to our benefit. An immutable is one that cannot be changed, you can not add to it, delete from it, or even change its value. Now you are probably asking, why can I add to a list, this is done all the time in the code. The answer is that the original list is left on the stack and a new list is constructed using the original list and the item to be added. Yes this is more work than necessary, but that's how it works. From my perspective with regards to provability of code, its worth the price. So to get the output list it is better to create the list starting from an empty list than to modify an existing list. That is why in the examples I gave you never saw a delete function.
So we know how to look at each item in a list individually with recursion. If this doe not make sense then just play with this on some list of different types and only print the values. Learning recursion for most people is one of those things were you struggle for a while then all at once you get it.
let rec processlist list =
match list with
| head :: tail ->
do something with head, e.g. print head
processlist tail
| []
and we have to make a decision when we have a head and the other list b
if (memberof b hd) the
which gets us to this
let common (a : 'a list) (b : 'a list) : 'a list =
let aUnique = isolate a
let bUnique = isolate b
let rec commonInner a b acc =
match list with
| head :: tail ->
if (memberof b head) then
do something
commInner tail acc
else
do something different
commonInner tail acc
| [] -> acc
commonInner aUnique bUnique []
When the head from a is in list b then we want to add it to the accumulator, acc which will become the output list.
When the head from a is NOT in list b then we do NOT want to add it to the accumulator, acc which will become the output list.
let common (a : 'a list) (b : 'a list) : 'a list =
let aUnique = isolate a
let bUnique = isolate b
let rec commonInner a b acc =
match list with
| head :: tail ->
if (memberof b head) then
let acc = head :: acc
commInner tail acc
else
commonInner tail acc
| [] -> acc
commonInner aUnique bUnique []
and lastly since the accumulator has the output list in a backward order because of the use of ::, we just use reverse to reverse the list before returning the result.
let common (a : 'a list) (b : 'a list) : 'a list =
let aUnique = isolate a
let bUnique = isolate b
let rec commonInner a b acc =
match list with
| head :: tail ->
if (memberof b head) then
let acc = head :: acc
commInner tail acc
else
commonInner tail acc
| [] -> reverse acc
commonInner aUnique bUnique []
here is the working code
// Reverse the order of the items in a list.
// val reverse : l:'a list -> 'a list
let reverse l =
let rec reverseInner l acc =
match l with
| x::xs ->
let acc = x :: acc
reverseInner xs acc
| [] -> acc
reverseInner l []
// Predicate that returns true if item is a member of the list.
// val memberof : l:'a list -> item:'a -> bool when 'a : equality
let memberof l item =
let rec memberInner l item =
match l with
| x::xs ->
if x = item then
true
else
memberInner xs item
| [] -> false
memberInner l item
// Return a list of unique items.
// val isolate : list:'a list -> 'a list when 'a : equality
let isolate list =
let rec isolateInner searchList commonlist =
match searchList with
| x::xs ->
if (memberof commonlist x) then
isolateInner xs commonlist
else
let commonlist = (x :: commonlist)
isolateInner xs commonlist
| [] -> reverse commonlist
isolateInner list []
// val common : a:'a list -> b:'a list -> 'a list when 'a : equality
let common a b =
let aUnique = isolate a
let bUnique = isolate b
let rec commonInner a b acc =
match a with
| x::xs ->
if memberof b x then
let acc = x :: acc
commonInner xs b acc
else
commonInner xs b acc
| [] -> reverse acc
commonInner aUnique bUnique []
common [1.0;2.0;3.0;4.0;5.0] [4.0;3.0;9.0] // val it : float list = [3.0; 4.0]
As far as I understand the requirements of this function, it ought to return the intersection of two lists. Since this is a set-based operation, it's already built-in to F#:
> set [1.0;2.0;3.0;4.0;5.0] |> Set.intersect (set [4.0;3.0;9.0]);;
val it : Set<float> = set [3.0; 4.0]
So, to do this recursively with lists, you need something like this:
let common a b =
let rec commonRec a b =
match a with
| [] -> [] // a is empty : no elements can be common so return empty list
| x::xs ->
if memberof x b then x :: commonRec xs b // if x is a member of b, keep it
else commonRec xs b // otherwise continue with remaining elements
commonRec (isolate a) (isolate b) // remove duplicates here
Notice that I have removed isolate from the recursive function, it only needs to be performed once at the start.
Since you didn't post code for the isolate or memberof functions, I don't want to make assumptions about what they might be from other questions or this answer won't be useful to anyone else. Of course, you can freely use a different implementation of the same functions.
I just made the following simple definitions:
let isolate lst =
lst |> Set.ofList |> Set.toList
let memberof a list =
List.contains a list
Result:
[1.0; 2.0; 3.0; 4.0; 5.0]
[4.0; 3.0; 9.0]
----> [3.0; 4.0]
