In this post I will talk about the lists in F#, one of the fundamental concepts of the language. What should be said from the very beginning is that list are imutable single linked list. That means whenever you change a list, a new list is created.<\/p>\n
You can declare a list in the following ways:<\/p>\n
\nlet list1 = [1;2;3;4]
\nlet list2 = 5::6::7::8::[]
\n<\/PRE><\/p>\nTo print the content of the list you can do this:<\/p>\n
\nprintfn “list1: %a” output_any list1
\nprintfn “list2: %a” output_any list2
\n<\/PRE><\/p>\n\r\nlist1: [1; 2; 3; 4]\r\nlist2: [5; 6; 7; 8]\r\n<\/PRE>\r\nYou can concatenate two lists with operator @:<\/p>\r\n
\r\nlet list3 = list1 @ list2\r\nprintfn \"list3: %a\" output_any list3\r\n<\/PRE>\r\n\r\nlist3: [1; 2; 3; 4; 5; 6; 7; 8]\r\n<\/pre>\nand you can append elements to the beginning of the list with operator ::<\/p>\n
\nlet list4 = -1::0::list3
\nprintfn \"list4: %a\" output_any list4
\n<\/PRE><\/p>\n\r\nlist4: [-1; 0; 1; 2; 3; 4; 5; 6; 7; 8]\r\n<\/pre>\nYou can also use the List (defined in Microsoft.FSharp.Code) functionality to print a list by iterating over its elements:<\/p>\n
\nlist3: [1; 2; 3; 4; 5; 6; 7; 8]
\n<\/PRE>
\n
\n1 2 3 4
\n<\/PRE><\/p>\nThe same can be achieved using the pipe operator:<\/p>\n
\nlist1 |> List.iter (fun x -> printf \"%d \" x)
\n<\/PRE><\/p>\nYou can also iterate and get the index of the list elements, with List.iteri:<\/p>\n
\r\nlist1 |> List.iteri (fun i x -> printfn \"list1[%d] : %d \" i x)\r\n<\/PRE>\r\n\r\nlist1[0] : 1\r\nlist1[1] : 2\r\nlist1[2] : 3\r\nlist1[3] : 4\r\n<\/PRE>\r\n\r\nList have a special representation, a head followed by a tail, that is in turn another list (including empty list []). Let's consider the list [1;2;3]. It has the head 1, and the tail [2;3]. The tail, in turn, has the head 2 and the tail [3]. This tail has the head 3 and the tail [], which is the empty list.\r\nYou can see the head and tail of a list with List.hd and List.td:<\/p>\r\n
\r\nprintfn \"head list1: %a\" output_any (List.hd list1)\r\nprintfn \"tail list1: %a\" output_any (List.tl list1)\r\n<\/PRE>\r\nThe ouput for list1 [1;2;3] is:<\/p>\r\n
\r\nhead list1: 1\r\ntail list1: [2;3]\r\n<\/pre>\nEnough with basic things. Let's try working with lists.<\/p>\n
1. Minimum and maximum from a list<\/h3>\n
We can compute the maximum (or minimum) of a list using the following algorithm:<\/p>\n
That sounds like a recursive operation, which can be simply put in F# like this:<\/p>\n
\nlet rec greatest_element l =
\n match l with
\n | [] -> failwith \"empty list\"
\n | [x] -> x
\n | x::rest -> max x (greatest_element rest)<\/p>\nlet rec smallest_element l =
\n match l with
\n | [] -> failwith \"empty list\"
\n | [x] -> x
\n | x::rest -> min x (smallest_element rest)
\n<\/PRE><\/p>\nWe can use that like this:<\/p>\n
\nlet list1 = [1;2;3;4;-4;-3;-2;-1]
\nlet list2 = [] <\/p>\ntry
\n printfn \"maximum from list1: %d\" (greatest_element list1)
\n printfn \"minimum from list1: %d\" (smallest_element list1)<\/p>\nprintfn \"maximum from list2: %d\" (greatest_element list2)
\n printfn \"minimum from list2: %d\" (smallest_element list2)
\nwith
\n Failure msg ->
\n printfn \"Error: %s\" msg
\n<\/PRE><\/p>\nand the output would be:<\/p>\n
\nmaximum from list1: 4
\nminimum from list1: -4
\nError: empty list
\n<\/PRE><\/p>\n2. Reversing a list<\/h3>\n
How would we reverse a list? We should take the last element and append to it the one before the last. To the new list we append the one before the one before the end, etc. That again sounds recursive.<\/p>\n
\nlet rec revert_list l =
\n match l with
\n | [] -> []
\n | x::rest -> (revert_list rest) @ [x]<\/p>\nlet list1 = [1;2;3;4;-4;-3;-2;-1]<\/p>\n
printfn \"list1: %a\" output_any list1
\nprintfn \"list2: %a\" output_any (revert_list list1)
\n<\/PRE><\/p>\nAnd here is the output:<\/p>\n
\nlist1: [1; 2; 3; 4; -4; -3; -2; -1]
\nlist2: [-1; -2; -3; -4; 4; 3; 2; 1]
\n<\/PRE><\/p>\n3. Inserting in a list<\/h3>\n
So how could we insert an element in a list, before or after a specified element? We can use the following algorithm:<\/p>\n
You got that right, recursion again.<\/p>\n
\nlet rec insert_after elem newelem l =
\n match l with
\n | [] -> [newelem]
\n | x::rest -> if x = elem then
\n (x::newelem::rest)
\n else
\n x::(insert_after elem newelem rest)<\/p>\nlet rec insert_before elem newelem l =
\n match l with
\n | [] -> [newelem]
\n | x::rest -> if x = elem then
\n (newelem::x::rest)
\n else
\n x::(insert_before elem newelem rest) <\/p>\nlet list1 = [1;2;3;4;-4;-3;-2;-1]
\nlet list2 = insert_after 4 6 list1
\nlet list3 = insert_before 6 5 list2<\/p>\nprintfn \"list1: %a\" output_any list1
\nprintfn \"list2: %a\" output_any list2
\nprintfn \"list3: %a\" output_any list3
\n<\/PRE><\/p>\nAnd the output is:<\/p>\n
\nlist1: [1; 2; 3; 4; -4; -3; -2; -1]
\nlist2: [1; 2; 3; 4; 6; -4; -3; -2; -1]
\nlist3: [1; 2; 3; 4; 5; 6; -4; -3; -2; -1]
\n<\/PRE><\/p>\n4. Removing elements from a list<\/h3>\n
As a last exercise, let's consider the removing of elements from a list. The following steps can be used to remove elements:<\/p>\n
\nlet rec remove_if l predicate =
\n match l with
\n | [] -> []
\n | x::rest -> if predicate(x) then
\n (remove_if rest predicate)
\n else
\n x::(remove_if rest predicate)
\n<\/PRE><\/p>\nThe great thing about this implementation is that we can pass a lambda expression as a predicate, and use it to specify the criteria for removing elements. We can remove like that, for instance, the odd elements, or the even elements, or the negative elements. Here is some sample code:<\/p>\n
\nlet list1 = [1;2;3;4;-4;-3;-2;-1]<\/p>\nlet list2 = remove_if list1 (fun x -> (abs x &&&1) = 1)
\nlet list3 = remove_if list1 (fun x -> (abs x &&&1) = 0)
\nlet list4 = remove_if list1 (fun x -> x < 0)\n\nprintfn \"%a\" output_any list1\nprintfn \"%a\" output_any list2\nprintfn \"%a\" output_any list3\nprintfn \"%a\" output_any list4\n<\/PRE><\/p>\nThe output for this sample is:<\/p>\n
\n[1; 2; 3; 4; -4; -3; -2; -1]
\n[2; 4; -4; -2]
\n[1; 3; -3; -1]
\n[1; 2; 3; 4]
\n<\/PRE><\/p>\nI hope this will help you to get a grip on how you can work on lists in F#.<\/p>\n","protected":false},"excerpt":{"rendered":"
In this post I will talk about the lists in F#, one of the fundamental concepts of the language. What should be said from the very beginning is that list are imutable single linked list. That means whenever you change a list, a new list is created. You can declare a list in the following … 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,38],"tags":[39],"class_list":["post-108","post","type-post","status-publish","format-standard","hentry","category-fsharp","category-tutorials","tag-f-tutorial-article-list-recursive"],"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