In this post I want to show how you can implement common list operations: union, intersection, difference and concatenation.<\/p>\n
Concatenation is the simplest of them all, because type List already has a function call append that does everything for you.<\/p>\n
\r\nlet concat left right =\r\n List.append left right\r\n<\/pre>\nThe union of two lists is a list containing all the distinct elements from the two original lists. We can implement this operation by concatenating the two lists firsts, and the filtering the distinct elements.<\/p>\n
\r\nlet union left right =\r\n List.append left right |> Seq.distinct |> List.ofSeq\r\n<\/pre>\nThe intersection of two lists is a list containing all the elements of the first list that also appear in the second list. We can implement this by interating through the elements of the first list and checking whether the element appears in the second list. To do this in the shortest possible time, with constant lookup time, we can use a HashSet collection. The result is an O(m+n) complexity instead of O(m*n) if you used brute force.<\/p>\n
\r\nlet intersection (left:list< 'a >) (right:list< 'a >) =\r\n let cache = HashSet< 'a >(right, HashIdentity.Structural)\r\n left |> List.filter (fun n -> cache.Contains n)\r\n<\/pre>\nThe difference of two lists is a list containing all the elements from the first list that are not part of the second list. The implementation of difference is very similar to the implementation of the intersection. All that differs is the lambda used for the filtering. <\/p>\n
\r\nlet difference (left:list< 'a >) (right:list< 'a >) =\r\n let cache = HashSet< 'a >(right, HashIdentity.Structural)\r\n left |> List.filter (fun n -> not (cache.Contains n))\r\n<\/pre>\nLet’s see all these put to a use:<\/p>\n
\r\nlet main() =\r\n let c = concat [4;3;2;1] [2;3;5]\r\n printfn \"%A\" c\r\n \r\n let u = union [4;3;2;1] [2;3;5]\r\n printfn \"%A\" u\r\n \r\n let i = intersection [4;3;2;2;1] [2;3;5]\r\n printfn \"%A\" i\r\n\r\n let d = difference [4;3;2;1] [2;3;5]\r\n printfn \"%A\" d\r\n \r\nmain()\r\n<\/pre>\nThis program yields the following output:<\/p>\n
\r\n[4; 3; 2; 1; 2; 3; 5]\r\n[4; 3; 2; 1; 5]\r\n[3; 2; 2]\r\n[4; 1]\r\n<\/pre>\nNotice that these operations work with unsorted lists. You don’t have to sort the lists first to apply them. <\/p>\n
In order to use the HashSet, you need to add a reference to the FSharp.PowerPack.dll assembly. This sample was build with F# 1.9.7.8 for Visual Studio 2008.<\/p>\n
UPDATE: You can read about similar implementations but using operators on this post by Jason Kikel<\/a>. He also deals with repetitions, regular expression binding operator and null coalescing binding operator.<\/p>\n","protected":false},"excerpt":{"rendered":"
In this post I want to show how you can implement common list operations: union, intersection, difference and concatenation. Concatenation is the simplest of them all, because type List already has a function call append that does everything for you. let concat left right = List.append left right The union of two lists is a … Read more<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_uag_custom_page_level_css":"","advgb_blocks_editor_width":"","advgb_blocks_columns_visual_guide":"","_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_feature_clip_id":0,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"jetpack_post_was_ever_published":false},"categories":[37],"tags":[50,179],"class_list":["post-412","post","type-post","status-publish","format-standard","hentry","category-fsharp","tag-f","tag-list"],"aioseo_notices":[],"aioseo_head":"\n\t\t\n\t\n\t\n\t\n\t\n\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t