f# remove from own user defined list -

i want create function removes occurrence of integer n , returns list. know how want not know command delete it.

here data type

type alist =         | l of int * alist 

here's how data type looks:

let l = l(2, l(1, l(2, l(7, l(3, l(2, a))))))  remove 2 l;; 

should return

l = l(1, l(7, l(3, a))) 

here have far:

let rec remove n l =      match (n, l)     | (n, a) -> l     | (n, l(head,tail)) when (n = head) ->  

i don't know how how rid of list or element.

you shouldn't thinking in terms of "deleting" list; should instead think in terms of building new list, without element want removed. i'll show how in minute, first want make suggestion. in match expression, re-using name n in patterns. that's classic beginner's mistake, because ends confusing you. once know f# pretty well, that's valid technique, since appear beginner, suggest not doing that. instead, use name in patterns different name of thing you're matching against, because teach something. let's rewrite match expression x name of int in patterns:

let rec remove n l =      match (n, l)     | (x, a) -> l     | (x, l(head,tail)) when (x = head) ->  

what each of these 2 patterns doing assigning name x represent value of n if rest of pattern matches. can more see first pattern doesn't use value of x @ all, better represent _ in case (_ "wildcard" pattern, means "i don't care value in position). thus, match expression become:

let rec remove n l =      match (n, l)     | (_, a) -> l     | (x, l(head,tail)) when (x = head) -> // ... still need write 

now let's think want in second match case. here have node precisely kind of node want remove list. how go building list without node in it? well, happens, already have such list... , we've assigned name tail in second match case. @ first, might this:

let rec remove n l =      match (n, l)     | (_, a) -> l     | (x, l(head,tail)) when (x = head) -> tail 

this return list "head" node chopped off. wait! if tail contained 1 or more nodes value want removed? we'd really return match case tail, passed through function remove nodes match value. but... wait minute... aren't writing function right now? if call remove on tail , have rest of work us; wouldn't nice?

well, turns out can! have remove rest of unwanted values tail list call remove on it! so:

let rec remove n l =      match (n, l)     | (_, a) -> l     | (x, l(head,tail)) when (x = head) -> remove n tail 

but we're not quite done yet, because there's 1 more possibility in match statement. if using f# development environment (i recommend visual studio code ionide plugin), should see green wavy underline under match keyword, , if hover on should see warning incomplete match expression. that's because there's 1 case haven't accounted for: case l node isn't a, head value isn't equal n. in other words, match case:

    | (x, l(head,tail)) when (x <> head) -> // here? 

well, starters, let's simplify match case bit. if put complete match expression, should see when guard unnecessary. match cases checked top bottom, in order. means if third match case, already know x must not equal head; otherwise second match case have been chosen! may not able see why yet, let's put match case our match expression , take @ it:

let rec remove n l =      match (n, l)     | (_, a) -> l     | (x, l(head,tail)) when (x = head) -> remove n tail     | (x, l(head,tail)) when (x <> head) -> // here? 

now it's more obvious previous match case, opposite when guard. means if ever reach third match case, when expression must true -- because if false, means x equal head , have gone down second match case, not third.

therefore, can remove when guard third match case, this:

let rec remove n l =      match (n, l)     | (_, a) -> l     | (x, l(head,tail)) when (x = head) -> remove n tail     | (x, l(head,tail)) -> // here? 

there's more simplification can done here, it's time @ result want return. here, not want skip first node of list, we'd still remove n tail. in fact, want result of function list node containing same head our current list node, tail has had n removed it. (if don't understand last sentence, take minute , try picture in head.) how this? well, simplest way follows:

let newtail = remove n tail l(head, newtail) 

which can simplified to:

l(head, remove n tail) 

so match function looks now:

let rec remove n l =      match (n, l)     | (_, a) -> l     | (x, l(head,tail)) when (x = head) -> remove n tail     | (x, l(head,tail)) -> l(head, remove n tail) 

believe or not, we're done! well, almost: have working function now, it's more complicated needs be. antoine de saint-exupéry well-known writing the little prince, aviator, has famous quote design:

il semble que la perfection soit atteinte non quand il n'y plus rien à ajouter, mais quand il n'y plus rien à retrancher.

in english, that's:

it seems perfection attained not when there nothing more add, when there nothing more remove.

so can remove function pare down absolute essentials? well, let's start looking @ last match case again:

    | (x, l(head,tail)) -> l(head, remove n tail) 

it looks don't use value of x anywhere in match case, don't need assign name int in match case. can use wildcard _ here. once do, our function looks like:

let rec remove n l =      match (n, l)     | (_, a) -> l     | (x, l(head,tail)) when (x = head) -> remove n tail     | (_, l(head,tail)) -> l(head, remove n tail) 

and @ point, might think we're done, because do use value of x in second match case, can't rid of it. or... can we? let's @ second match case more closely:

    | (x, l(head,tail)) when (x = head) -> remove n tail 

now. value of x here same value of n, because match case assigning value of n name x virtue of x being in first tuple position. right? in when guard, could swap out x n in x = head check. legal: checks in match case not have include names have appeared in match pattern. can any names function has access to. it's valid swap x out n , match case this:

    | (x, l(head,tail)) when (n = head) -> remove n tail 

and see we're not using value of x in match case either, in third match case. let's rid of it:

    | (_, l(head,tail)) when (n = head) -> remove n tail 

now let's put match case our function , take @ function whole:

let rec remove n l =      match (n, l)     | (_, a) -> l     | (_, l(head,tail)) when (n = head) -> remove n tail     | (_, l(head,tail)) -> l(head, remove n tail) 

huh. @ that? first tuple item has "i don't care" in every single spot in match case. , yet, function still compiles without warning incomplete match patterns, , still runs , produces correct values. (try it!) tell us? tells don't need have n in value we're matching against, because never need in match patterns. need in when guards, not in match patterns themselves! if remove n value we're matching against, , match patterns, here's result:

let rec remove n l =      match l     | -> l     | l(head,tail) when (n = head) -> remove n tail     | l(head,tail) -> l(head, remove n tail) 

try it. you'll see function compiles, , still want do.

at point, are done. taking away anything else function break it: either wouldn't compile, or else wouldn't return right value. may not obvious you, skill f# grows, you'll learn feel when function has been pared down bare essentials, , 1 has.

and there go: after lot of tweaking, we've gotten remove function not working, working elegantly. simplest can possibly make function, , there's beauty in that. if can see , appreciate beauty, beauty of function should , no more, you'll on way becoming skilled f# programmer!

p.s. there 1 more rewrite could on function, because better. stands, function not tail-recursive, means if called on large list, stackoverflowexception. if haven't reached point of studying tail recursion yet, trying explain how fix problem confuse rather understand things better. i've deliberately chosen end pared-down, elegant version of function, rather version tail recursion "properly". because making that improvement produce function more complicated , harder understand. once you're more experienced f#, it'll worth revisiting question , asking "how make function tail-recursive?". now, non-tail-recursive version have here 1 should study. once understand how write function on own, , can write other list-manipulation functions on user-defined list data structure, you'll have knowledge needed make last improvement.

i hope helps. please leave comment asking me don't understand in explanation.