Finding matching pairs in two sequences

Here's a function which takes a comparator function and two sequences, and returns tuples consisting of an item from each sequence, where the comparator function returns true for those two items. This is a small part of my wider project to generate guitar chord shapes. One of the requirements there is to take a list of 'wanted' notes for a chord, and a list of 'available' notes within a range of frets and to combine them into an actual set of frettings. That's what led to tryFindFirstPair and hence to findPairs.

 1: /// Given two sequences and a comparator function, find the pairs of items for 
 2: /// which the comparator returns true
 3: let findPairs compare seqT seqU =
 4:     seq {
 5:             for t in seqT do
 6:                 for u in seqU do
 7:                     if (compare t u) then
 8:                         yield (t, u)
 9:     }
10: 
11: /// Given two sequences and a comparator function, find the first pair of items 
12: /// for which the comparator returns true
13: let tryFindFirstPair compare seqT seqU =
14:     let matches = findPairs compare seqT seqU
15:     if not (Seq.isEmpty matches) then
16:         Some(Seq.nth 0 matches)
17:     else
18:         None
19: 
20: //// A quick demo to generate lists of rhyming words:
21: 
22: /// Reverse a string (from TomasP):
23: let reverse (s:string) =
24:   let rec reverseAux idx acc =
25:     if (idx = s.Length) then acc
26:     else reverseAux (idx+1) ((s.[idx])::acc)
27:   new string(Array.ofList (reverseAux 0 []))
28: 
29: /// A crude way to work out the last syllable for a word:
30: let lastSyllable word =
31:     let vowels = [|'a';'e';'i';'o';'u';'y'|]
32:     let wordRev = reverse word
33:     let vowelPos = wordRev.IndexOfAny(vowels, 1)
34:     let lastSylRev = wordRev.Substring(0, vowelPos+1)
35:     reverse lastSylRev
36: 
37: /// Return true when words might rhyme based on their final syllables being 
38: /// the same
39: let mightRhyme wordA wordB =
40:     (wordA <> wordB) && (lastSyllable wordA = lastSyllable wordB)
41: 
42: /// Two steams of words, some of which might rhyme
43: let words1 = ["orange"; "purple"; "hubble"; "indicative"; "mandatory"]
44: let words2 = ["hurple"; "rhubarb"; "tory"; "bubble"]
45: 
46: /// Find the rhymes
47: findPairs mightRhyme words1 words2
48: 
49: // Output: seq [("purple", "hurple"); ("hubble", "bubble"); ("mandatory", "tory")]
50: 
51: /// Find the rhymes in a single stream of words:
52: let wordsAll = ["orange"; "purple"; "hubble"; "indicative"; "mandatory"; "hurple"; "rhubarb"; "tory"; "bubble"]
53: findPairs mightRhyme wordsAll wordsAll
54: 
55: // Output: seq
56: //    [("purple", "hurple"); ("hubble", "bubble"); ("mandatory", "tory");
57: //     ("hurple", "purple"); ...]

val findPairs : ('a -> 'b -> bool) -> seq<'a> -> seq<'b> -> seq<'a * 'b>

Full name: Snippet.findPairs

Given two sequences and a comparator function, find the pairs of items for
which the comparator returns true

val compare : ('a -> 'b -> bool)

val seqT : seq<'a>

type: seq<'a>
inherits: System.Collections.IEnumerable

val seqU : seq<'b>

type: seq<'b>
inherits: System.Collections.IEnumerable

Multiple items
val seq : seq<'T> -> seq<'T>

Full name: Microsoft.FSharp.Core.Operators.seq

--------------------

type seq<'T> = System.Collections.Generic.IEnumerable<'T>

Full name: Microsoft.FSharp.Collections.seq<_>

type: seq<'T>
inherits: System.Collections.IEnumerable

val t : 'a

val u : 'b

val tryFindFirstPair : ('a -> 'b -> bool) -> seq<'a> -> seq<'b> -> ('a * 'b) option

Full name: Snippet.tryFindFirstPair

Given two sequences and a comparator function, find the first pair of items
for which the comparator returns true

val matches : seq<'a * 'b>

type: seq<'a * 'b>
inherits: System.Collections.IEnumerable

val not : bool -> bool

Full name: Microsoft.FSharp.Core.Operators.not

module Seq

from Microsoft.FSharp.Collections

val isEmpty : seq<'T> -> bool

Full name: Microsoft.FSharp.Collections.Seq.isEmpty

union case Option.Some: 'T -> Option<'T>

val nth : int -> seq<'T> -> 'T

Full name: Microsoft.FSharp.Collections.Seq.nth

union case Option.None: Option<'T>

val reverse : string -> string

Full name: Snippet.reverse

Reverse a string (from TomasP):

val s : string

  type: string
  implements: System.IComparable
  implements: System.ICloneable
  implements: System.IConvertible
  implements: System.IComparable<string>
  implements: seq<char>
  implements: System.Collections.IEnumerable
  implements: System.IEquatable<string>

Multiple items
val string : 'T -> string

Full name: Microsoft.FSharp.Core.Operators.string

--------------------

type string = System.String

Full name: Microsoft.FSharp.Core.string

  type: string
  implements: System.IComparable
  implements: System.ICloneable
  implements: System.IConvertible
  implements: System.IComparable<string>
  implements: seq<char>
  implements: System.Collections.IEnumerable
  implements: System.IEquatable<string>

val reverseAux : (int -> char list -> char list)

val idx : int

  type: int
  implements: System.IComparable
  implements: System.IFormattable
  implements: System.IConvertible
  implements: System.IComparable<int>
  implements: System.IEquatable<int>
  inherits: System.ValueType

val acc : char list

  type: char list
  implements: System.Collections.IStructuralEquatable
  implements: System.IComparable<List<char>>
  implements: System.IComparable
  implements: System.Collections.IStructuralComparable
  implements: System.Collections.Generic.IEnumerable<char>
  implements: System.Collections.IEnumerable

property System.String.Length: int

module Array

from Microsoft.FSharp.Collections

val ofList : 'T list -> 'T []

Full name: Microsoft.FSharp.Collections.Array.ofList

val lastSyllable : string -> string

Full name: Snippet.lastSyllable

A crude way to work out the last syllable for a word:

val word : string

  type: string
  implements: System.IComparable
  implements: System.ICloneable
  implements: System.IConvertible
  implements: System.IComparable<string>
  implements: seq<char>
  implements: System.Collections.IEnumerable
  implements: System.IEquatable<string>

val vowels : char []

  type: char []
  implements: System.ICloneable
  implements: System.Collections.IList
  implements: System.Collections.ICollection
  implements: System.Collections.IStructuralComparable
  implements: System.Collections.IStructuralEquatable
  implements: System.Collections.Generic.IList<char>
  implements: System.Collections.Generic.ICollection<char>
  implements: seq<char>
  implements: System.Collections.IEnumerable
  inherits: System.Array

val wordRev : string

  type: string
  implements: System.IComparable
  implements: System.ICloneable
  implements: System.IConvertible
  implements: System.IComparable<string>
  implements: seq<char>
  implements: System.Collections.IEnumerable
  implements: System.IEquatable<string>

val vowelPos : int

  type: int
  implements: System.IComparable
  implements: System.IFormattable
  implements: System.IConvertible
  implements: System.IComparable<int>
  implements: System.IEquatable<int>
  inherits: System.ValueType

Multiple overloads
System.String.IndexOfAny(anyOf: char []) : int
System.String.IndexOfAny(anyOf: char [], startIndex: int) : int
System.String.IndexOfAny(anyOf: char [], startIndex: int, count: int) : int

val lastSylRev : string

  type: string
  implements: System.IComparable
  implements: System.ICloneable
  implements: System.IConvertible
  implements: System.IComparable<string>
  implements: seq<char>
  implements: System.Collections.IEnumerable
  implements: System.IEquatable<string>

Multiple overloads
System.String.Substring(startIndex: int) : string
System.String.Substring(startIndex: int, length: int) : string

val mightRhyme : string -> string -> bool

Full name: Snippet.mightRhyme

Return true when words might rhyme based on their final syllables being
the same

val wordA : string

  type: string
  implements: System.IComparable
  implements: System.ICloneable
  implements: System.IConvertible
  implements: System.IComparable<string>
  implements: seq<char>
  implements: System.Collections.IEnumerable
  implements: System.IEquatable<string>

val wordB : string

  type: string
  implements: System.IComparable
  implements: System.ICloneable
  implements: System.IConvertible
  implements: System.IComparable<string>
  implements: seq<char>
  implements: System.Collections.IEnumerable
  implements: System.IEquatable<string>

val words1 : string list

Full name: Snippet.words1

  type: string list
  implements: System.Collections.IStructuralEquatable
  implements: System.IComparable<List<string>>
  implements: System.IComparable
  implements: System.Collections.IStructuralComparable
  implements: System.Collections.Generic.IEnumerable<string>
  implements: System.Collections.IEnumerable

Two steams of words, some of which might rhyme

val words2 : string list

Full name: Snippet.words2

  type: string list
  implements: System.Collections.IStructuralEquatable
  implements: System.IComparable<List<string>>
  implements: System.IComparable
  implements: System.Collections.IStructuralComparable
  implements: System.Collections.Generic.IEnumerable<string>
  implements: System.Collections.IEnumerable

val wordsAll : string list

Full name: Snippet.wordsAll

  type: string list
  implements: System.Collections.IStructuralEquatable
  implements: System.IComparable<List<string>>
  implements: System.IComparable
  implements: System.Collections.IStructuralComparable
  implements: System.Collections.Generic.IEnumerable<string>
  implements: System.Collections.IEnumerable

Find the rhymes
Find the rhymes in a single stream of words:

More information

Link:	http://fssnip.net/75
Posted:	1 years ago
Author:	Kit Eason (website)
Tags:	learning F#, sequences

Finding matching pairs in two sequences

More information

Hosting

F# Snippets

License

Credits