I do not understand it well about Reduction in Haskell in this Function:
removeone :: Eq a = > a -> [ a ] -> [ a ]
removeone _ [] = []
removeone x ( y : ys )
| x == y = removeone x ys
| otherwise = y : ( removeone x ys )
remdups :: Eq a = > [ a ] -> [ a ]
remdups [] = []
remdups ( x : xs ) = x : remdups ( removeone x xs )
How could I use this function to explain Reduction steps in a List (for example remdups [3,7,3,7,5,7])?
Start by remdups [3,7,3,7,5,7] and simplify the expression as to the left as possible. Remember that [x,y,z] is a shorthand for x:y:z:[]. Hence remdups (3:7:....) = 3 : remdups (removeone 3 (7:....)) = ... and now youl need to use the definition of removeone since no equation of remdups applies. After removeone generates a : or [], you will return to simplifying the remdups call.
One row is one reduction. In the comments are row numbers with reduction codes. My example uses a Outermost (lazy) reduction.
remdups [3,7,3,7,5,7]
3:remdups (removeone 3 [7,3,7,5,7]) -- 9
3:remdups (7:(removeone 3 [3,7,5,7])) -- 5
3:7:remdups (removeone 7 (removeone 3 [3,7,5,7])) -- 9
3:7:remdups (removeone 7 (removeone 3 [7,5,7])) -- 4
3:7:remdups (removeone 7 (7:(removeone 3 [5,7]))) -- 5
3:7:remdups (removeone 7 (removeone 3 [5,7])) -- 4
3:7:remdups (removeone 7 (5:(removeone 3 [7]))) -- 5
3:7:remdups (5:(removeone 7 (removeone 3 [7]))) -- 5
3:7:5:remdups (removeone 5 (removeone 7 (removeone 3 [7]))) -- 9
3:7:5:remdups (removeone 5 (removeone 7 (7:(removeone 3 [])))) -- 5
3:7:5:remdups (removeone 5 (removeone 7 (removeone 3 []))) -- 4
3:7:5:remdups (removeone 5 (removeone 7 [])) -- 2
3:7:5:remdups (removeone 5 []) -- 2
3:7:5:remdups [] -- 2
3:7:5:[] -- 8
For completeness, there are other reduction procedures. For example leftmost-innermost (greedy) reduction. In this sample is the same result but for example head $ remdups [1..] greedy reduction would 'hang'. So as I know, that the leftmost-innermost is used only theoretically or for memory optimization:
remdups [3,7,3,7,5,7]
3:remdups (removeone 3 [7,3,7,5,7])
3:remdups (7:(removeone 3 [3,7,5,7]))
3:remdups (7:(removeone 3 [7,5,7]))
3:remdups (7:(7:(removeone 3 [5,7])))
3:remdups (7:(7:(5:(removeone 3 [7]))))
3:remdups (7:(7:(5:(7:(removeone 3 [])))))
3:remdups (7:(7:(5:(7:([])))))
3:remdups [7,7,5,7] -- shorthand
3:7:remdups (removeone 7 [7,5,7])
3:7:remdups (removeone 7 [5,7])
3:7:remdups (5:(removeone 7 [7]))
3:7:remdups (5:(removeone 7 []))
3:7:remdups (5:([]))
3:7:remdups [5] -- shorthand
3:7:5:remdups (removeone 5 [])
3:7:5:remdups ([])
3:7:5:remdups [] -- shorthand
3:7:5:[]
[3,7,5] -- shorthand