function unique

Alexteslin

10 Jul 2007 10 Jul '07

4:40 p.m.

Hi, i am a beginner to Haskell and i have a beginner's question to ask. An exercise asks to define function unique :: [Int] -> [Int], which outputs a list with only elements that are unique to the input list (that appears no more than once). I defined a function with list comprehension which works but trying to implement with pattern matching and primitive recursion with lists and doesn't work. unique :: [Int] -> [Int] unique xs = [x | x <- xs, elemNum2 x xs == 1] elemNum2 :: Int -> [Int] -> Int elemNum2 el xs = length [x| x <- xs, x == el] //This doesn't work, I know because the list shrinks and produces wrong result but can not get a right //thinking unique2 :: [Int] -> [Int] unique2 [] = [] unique2 (x:xs) |elemNum2 x xs == 1 = x:unique2 xs |otherwise = unique2 xs Any help to a right direction would be very appreciated, thanks. -- View this message in context: http://www.nabble.com/function-unique-tf4058328.html#a11528933 Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

Show replies by date

Brent Yorgey

10 Jul 10 Jul

4:52 p.m.

The problem with your second implementation is that elements which occur more than once will eventually be included, when the part of the list remaining only has one copy. For example: unique2 [1,1,2,4,1] = unique2 [1,2,4,1] = unique2 [2,4,1] = 2 : unique2 [4,1] = 2 : 4 : unique2 [1] = 2 : 4 : 1 : unique2 [] -- only a single 1 left, so it gets mistakenly included = [2,4,1] When you determine that a certain number should not be included in the output, you need to delete all remaining occurrences of it from the list, so it won't get included later. unique2 (x:xs) |elemNum2 x xs == 1 = x:unique2 xs |otherwise = unique2 (deleteElt x xs) I'll let you figure out how to implement the deleteElt function. hope this is helpful! -Brent On 7/10/07, Alexteslin wrote:

...

Hi, i am a beginner to Haskell and i have a beginner's question to ask.

An exercise asks to define function unique :: [Int] -> [Int], which outputs a list with only elements that are unique to the input list (that appears no more than once). I defined a function with list comprehension which works but trying to implement with pattern matching and primitive recursion with lists and doesn't work.

unique :: [Int] -> [Int] unique xs = [x | x <- xs, elemNum2 x xs == 1]

elemNum2 :: Int -> [Int] -> Int elemNum2 el xs = length [x| x <- xs, x == el]

//This doesn't work, I know because the list shrinks and produces wrong result but can not get a right //thinking

unique2 :: [Int] -> [Int] unique2 [] = [] unique2 (x:xs) |elemNum2 x xs == 1 = x:unique2 xs |otherwise = unique2 xs

Any help to a right direction would be very appreciated, thanks. -- View this message in context: http://www.nabble.com/function-unique-tf4058328.html#a11528933 Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

Alexteslin

5:07 p.m.

I'v got it - it produces the right output. Thank you. Brent Yorgey wrote:

...

The problem with your second implementation is that elements which occur more than once will eventually be included, when the part of the list remaining only has one copy. For example:

unique2 [1,1,2,4,1] = unique2 [1,2,4,1] = unique2 [2,4,1] = 2 : unique2 [4,1] = 2 : 4 : unique2 [1] = 2 : 4 : 1 : unique2 [] -- only a single 1 left, so it gets mistakenly included = [2,4,1]

When you determine that a certain number should not be included in the output, you need to delete all remaining occurrences of it from the list, so it won't get included later.

unique2 (x:xs) |elemNum2 x xs == 1 = x:unique2 xs |otherwise = unique2 (deleteElt x xs)

I'll let you figure out how to implement the deleteElt function.

hope this is helpful! -Brent

On 7/10/07, Alexteslin wrote:

...
Hi, i am a beginner to Haskell and i have a beginner's question to ask.

An exercise asks to define function unique :: [Int] -> [Int], which outputs a list with only elements that are unique to the input list (that appears no more than once). I defined a function with list comprehension which works but trying to implement with pattern matching and primitive recursion with lists and doesn't work.

unique :: [Int] -> [Int] unique xs = [x | x <- xs, elemNum2 x xs == 1]

elemNum2 :: Int -> [Int] -> Int elemNum2 el xs = length [x| x <- xs, x == el]

//This doesn't work, I know because the list shrinks and produces wrong result but can not get a right //thinking

unique2 :: [Int] -> [Int] unique2 [] = [] unique2 (x:xs) |elemNum2 x xs == 1 = x:unique2 xs |otherwise = unique2 xs

Any help to a right direction would be very appreciated, thanks. -- View this message in context: http://www.nabble.com/function-unique-tf4058328.html#a11528933 Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

-- View this message in context: http://www.nabble.com/function-unique-tf4058328.html#a11529400 Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

Dan Weston

6:42 p.m.

Alexteslin wrote:

...

I'v got it - it produces the right output. Thank you.

Now that you've done the exercise, the fun starts! What assumptions did you build in to your solution? 1) You just need uniqueness, so counting the number of copies is not only overkill, but requires you to go through the entire list to count them. 2) The list might be infinite, and your function should work if you make only want to use the first part of it, so the following should return [1,2,3,4,5] in a finite amount of time: take 5 (unique [1..]) Your algorithm fails both of these. Consider a *lazy* approach: 1) Keep the head of the list 2) Then filter the tail, keeping only elements different from the head 3) Then put the two together Don't worry in step #2 about having an infinite number of list elements to be filtered out of the list. Think of it like asking a lazy child to clean the house. They're only going to do it just before mom gets home (who knows, with any luck she'll be in a car crash and forget about having asked you to clean!) This works for infinite lists, and puts off the work until you actually need the elements. I won't cheat you out of the fun, but here's the solution to a *very* similar problem using the Sieve of Eratosthenes to find prime numbers: isNotDivisor divisor dividend = dividend `rem` divisor /= 0 keepOnlyLowestMultiple (x:xs) = x : keepOnlyLowestMultiple (filter (isNotDivisor x) xs) primes = keepOnlyLowestMultiple [2..] Dan

...

Brent Yorgey wrote:

...
The problem with your second implementation is that elements which occur more than once will eventually be included, when the part of the list remaining only has one copy. For example:

unique2 [1,1,2,4,1] = unique2 [1,2,4,1] = unique2 [2,4,1] = 2 : unique2 [4,1] = 2 : 4 : unique2 [1] = 2 : 4 : 1 : unique2 [] -- only a single 1 left, so it gets mistakenly included = [2,4,1]

When you determine that a certain number should not be included in the output, you need to delete all remaining occurrences of it from the list, so it won't get included later.

unique2 (x:xs) |elemNum2 x xs == 1 = x:unique2 xs |otherwise = unique2 (deleteElt x xs)

I'll let you figure out how to implement the deleteElt function.

hope this is helpful! -Brent

On 7/10/07, Alexteslin wrote:

...
Hi, i am a beginner to Haskell and i have a beginner's question to ask.

An exercise asks to define function unique :: [Int] -> [Int], which outputs a list with only elements that are unique to the input list (that appears no more than once). I defined a function with list comprehension which works but trying to implement with pattern matching and primitive recursion with lists and doesn't work.

unique :: [Int] -> [Int] unique xs = [x | x <- xs, elemNum2 x xs == 1]

elemNum2 :: Int -> [Int] -> Int elemNum2 el xs = length [x| x <- xs, x == el]

//This doesn't work, I know because the list shrinks and produces wrong result but can not get a right //thinking

unique2 :: [Int] -> [Int] unique2 [] = [] unique2 (x:xs) |elemNum2 x xs == 1 = x:unique2 xs |otherwise = unique2 xs

Any help to a right direction would be very appreciated, thanks. -- View this message in context: http://www.nabble.com/function-unique-tf4058328.html#a11528933 Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

Alexteslin

11 Jul 11 Jul

11:55 a.m.

Thank you for your great suggestions, i will try to use lazy evaluation of course. But as a beginner I am on Chapter 7 of the textbook and will soon (perhaps in few weeks) move on to that, which is Chapter 17. And as I really would like to master the language I would not jump straight to that. My unique looks like this: unique2 :: [Int] -> [Int] unique2 [] = [] unique2 (x:xs) |elem x xs = unique2 (deleteElem x xs) |otherwise = x:unique2 xs deleteElem :: Int -> [Int] -> [Int] deleteElem x [] = [] deleteElem x (y:ys) |x == y = deleteElem x ys |otherwise = y:deleteElem x ys And I did think about for every call it will go through an entire list - now i know where the solution lies. Thanks again Dan Weston wrote:

...

Alexteslin wrote:

...
I'v got it - it produces the right output. Thank you.

Now that you've done the exercise, the fun starts! What assumptions did you build in to your solution?

1) You just need uniqueness, so counting the number of copies is not only overkill, but requires you to go through the entire list to count them.

2) The list might be infinite, and your function should work if you make only want to use the first part of it, so the following should return [1,2,3,4,5] in a finite amount of time:

take 5 (unique [1..])

Your algorithm fails both of these. Consider a *lazy* approach:

1) Keep the head of the list 2) Then filter the tail, keeping only elements different from the head 3) Then put the two together

Don't worry in step #2 about having an infinite number of list elements to be filtered out of the list. Think of it like asking a lazy child to clean the house. They're only going to do it just before mom gets home (who knows, with any luck she'll be in a car crash and forget about having asked you to clean!)

This works for infinite lists, and puts off the work until you actually need the elements.

I won't cheat you out of the fun, but here's the solution to a *very* similar problem using the Sieve of Eratosthenes to find prime numbers:

isNotDivisor divisor dividend = dividend `rem` divisor /= 0

keepOnlyLowestMultiple (x:xs) = x : keepOnlyLowestMultiple (filter (isNotDivisor x) xs)

primes = keepOnlyLowestMultiple [2..]

Dan

...
Brent Yorgey wrote:

...
The problem with your second implementation is that elements which occur more than once will eventually be included, when the part of the list remaining only has one copy. For example:

unique2 [1,1,2,4,1] = unique2 [1,2,4,1] = unique2 [2,4,1] = 2 : unique2 [4,1] = 2 : 4 : unique2 [1] = 2 : 4 : 1 : unique2 [] -- only a single 1 left, so it gets mistakenly included = [2,4,1]

When you determine that a certain number should not be included in the output, you need to delete all remaining occurrences of it from the list, so it won't get included later.

unique2 (x:xs) |elemNum2 x xs == 1 = x:unique2 xs |otherwise = unique2 (deleteElt x xs)

I'll let you figure out how to implement the deleteElt function.

hope this is helpful! -Brent

On 7/10/07, Alexteslin wrote:

...
Hi, i am a beginner to Haskell and i have a beginner's question to ask.

An exercise asks to define function unique :: [Int] -> [Int], which outputs a list with only elements that are unique to the input list (that appears no more than once). I defined a function with list comprehension which works but trying to implement with pattern matching and primitive recursion with lists and doesn't work.

unique :: [Int] -> [Int] unique xs = [x | x <- xs, elemNum2 x xs == 1]

elemNum2 :: Int -> [Int] -> Int elemNum2 el xs = length [x| x <- xs, x == el]

//This doesn't work, I know because the list shrinks and produces wrong result but can not get a right //thinking

unique2 :: [Int] -> [Int] unique2 [] = [] unique2 (x:xs) |elemNum2 x xs == 1 = x:unique2 xs |otherwise = unique2 xs

Any help to a right direction would be very appreciated, thanks. -- View this message in context: http://www.nabble.com/function-unique-tf4058328.html#a11528933 Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

-- View this message in context: http://www.nabble.com/function-unique-tf4058328.html#a11543116 Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

Brent Yorgey

2:41 p.m.

...

2) The list might be infinite, and your function should work if you make only want to use the first part of it, so the following should return [1,2,3,4,5] in a finite amount of time:

take 5 (unique [1..])

I don't think this is possible. Perhaps you misread the original problem description? The unique function is supposed to return a list of those elements which occur exactly once in the input list, which is impossible to determine for an infinite input list (the only way to prove that a given element occurs only once in a list, in the absence of any other information, is to examine every element of the list). Of course, a function that behaves like the unix utility "uniq" (i.e. returning only one copy of every list element) is possible to implement lazily in the manner you describe. @Alexteslin: It probably would still be a useful exercise for you, though, to get rid of the redundancy Dan describes in determining whether to keep each element. A function to count the occurrences of a given element (although useful in its own right) is overkill here, since you only care whether the element occurs once, or more than once. You could implement a function isUnique :: Int -> [Int] -> Bool which tells you whether the given element occurs only once (True) or more than once (False), and doesn't evaluate more of the list than necessary to determine this. I doubt you'd have much trouble implementing this function. -Brent

Antoine Latter

3:31 p.m.

On 7/11/07, Brent Yorgey wrote:

...

...
take 5 (unique [1..])

I don't think this is possible. Perhaps you misread the original problem description? The unique function is supposed to return a list of those elements which occur exactly once in the input list, which is impossible to determine for an infinite input list (the only way to prove that a given element occurs only once in a list, in the absence of any other information, is to examine every element of the list). Of course, a function that behaves like the unix utility "uniq" ( i.e. returning only one copy of every list element) is possible to implement lazily in the manner you describe.

Why wouldn't this work? (I haven't tested it, sorry) unique = unique' [] unique' _ [] = [] unique' history (x:xs) = if x `elem` history then next else (x:next) where next = (uniq' (x:hist) xs) Whether or not it's a good idea is a separate issue. Antoine

Neil Mitchell

3:34 p.m.

...

unique = unique' []

unique' _ [] = [] unique' history (x:xs) = if x `elem` history then next else (x:next) where next = (uniq' (x:hist) xs)

You can express this more neatly: unique' _ [] = [] unique' history (x:xs) = [x | x `notElem` history] ++ unique' (x:history) xs Thanks Neil

Alexteslin

3:59 p.m.

Oh, I am lost now - for now anyway. I am attempting to do next exercise in the book to define reverse function using primitive recursion and pattern matching on lists. But getting stack because when i con in front of xs (xs:x) i get en error, which i thought i would be getting anyway. I tried to define a helper function and cons there in front of xs and i get type errors again. I know these are easy and boring questions but i would appreciate a hint. Thank you Neil Mitchell wrote:

...

Hi

...
unique = unique' []

unique' _ [] = [] unique' history (x:xs) = if x `elem` history then next else (x:next) where next = (uniq' (x:hist) xs)

You can express this more neatly:

unique' _ [] = [] unique' history (x:xs) = [x | x `notElem` history] ++ unique' (x:history) xs

Thanks

Neil _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

-- View this message in context: http://www.nabble.com/function-unique-tf4058328.html#a11547781 Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

Brent Yorgey

4:11 p.m.

On 7/11/07, Alexteslin wrote:

...

Oh, I am lost now - for now anyway. I am attempting to do next exercise in the book to define reverse function using primitive recursion and pattern matching on lists. But getting stack because when i con in front of xs (xs:x) i get en error, which i thought i would be getting anyway. I tried to define a helper function and cons there in front of xs and i get type errors again.

I know these are easy and boring questions but i would appreciate a hint.

Thank you

Let's look at the type of the cons operator: Prelude> :t (:) (:) :: a -> [a] -> [a] That is, it takes an element of any type (here represented by 'a'), and a list of the same type, and produces a list. So (xs:x) does not make sense, assuming that xs is a list and x has the same type as an element of xs; cons expects an element followed by a list, and you are giving it a list followed by an element. If you want to append an element onto the end of a list you can do xs ++ [x] ++ is the list append operator, so this says "make x into a list with one element, and append it onto the end of the list xs". Does that help? It's hard to help without seeing any code or the specific errors you are seeing, but hopefully that should give you a push in the right direction. -Brent

Hugh Perkins

4:25 p.m.

Simple answer: you always have to have the single element first, then the list bit second. It's just the way it is. You can learn why later on ;-) On 7/11/07, Alexteslin wrote:

...

Oh, I am lost now - for now anyway. I am attempting to do next exercise in the book to define reverse function using primitive recursion and pattern matching on lists. But getting stack because when i con in front of xs (xs:x) i get en error, which i thought i would be getting anyway. I tried to define a helper function and cons there in front of xs and i get type errors again.

I know these are easy and boring questions but i would appreciate a hint.

Thank you

Neil Mitchell wrote:

...
Hi

...
unique = unique' []

unique' _ [] = [] unique' history (x:xs) = if x `elem` history then next else (x:next) where next = (uniq' (x:hist) xs)

You can express this more neatly:

unique' _ [] = [] unique' history (x:xs) = [x | x `notElem` history] ++ unique'

(x:history)

...
xs

Thanks

Neil _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

-- View this message in context: http://www.nabble.com/function-unique-tf4058328.html#a11547781 Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

Brent Yorgey

4:06 p.m.

...

...
I don't think this is possible. Perhaps you misread the original problem description? The unique function is supposed to return a list of those elements which occur exactly once in the input list, which is impossible to determine for an infinite input list (the only way to prove that a given element occurs only once in a list, in the absence of any other information, is to examine every element of the list). Of course, a function that behaves like the unix utility "uniq" ( i.e. returning only one copy of every list element) is possible to implement lazily in the manner you describe.

Why wouldn't this work? (I haven't tested it, sorry)

unique = unique' []

unique' _ [] = [] unique' history (x:xs) = if x `elem` history then next else (x:next) where next = (uniq' (x:hist) xs)

Again, this is solving a different problem than what the OP stated. Using your definition: Prelude> :l unique [1 of 1] Compiling Main ( unique.hs, interpreted ) Ok, modules loaded: Main. *Main> unique [1,2,3,1] [1,2,3] *Main> ...which behaves like the Unix utility 'uniq'. But the problem described originally is to write a function which produces [2,3] when given the same input; 1 is not included in the output since it occurs more than once. -Brent

Hugh Perkins

4:31 p.m.

Ok so I played with the tweaked problem (Unix 'uniq'), and getting it to be lazy. This seems to work: testunique :: Eq a => [a] -> [a] testunique list = testunique' list [] where testunique' :: Eq a => [a] -> [a] -> [a] testunique' [] elementssofar = [] testunique' (x:xs) elementssofar | x `elem` elementssofar = (testunique' elementssofar xs) | otherwise = x : ( testunique' xs (x:elementssofar)) Now, a question, why is this happening: doesnt block: take 10 (testunique ([1,3] ++ [7..])) take 10 (testunique ([7..] ++ [1,3,7])) blocks forever: take 10 (testunique ([1,3,7] ++ [7..])) The expression ([1,3,7] ++ [7..]) itself doesnt block: things like "take 10 ( [1,3,7] ++ [7 ..] )" work just fine, so what is going on? On 7/11/07, Dan Weston wrote:

...

Alexteslin wrote:

...
I'v got it - it produces the right output. Thank you.

Now that you've done the exercise, the fun starts! What assumptions did you build in to your solution?

1) You just need uniqueness, so counting the number of copies is not only overkill, but requires you to go through the entire list to count them.

2) The list might be infinite, and your function should work if you make only want to use the first part of it, so the following should return [1,2,3,4,5] in a finite amount of time:

take 5 (unique [1..])

Your algorithm fails both of these. Consider a *lazy* approach:

1) Keep the head of the list 2) Then filter the tail, keeping only elements different from the head 3) Then put the two together

Don't worry in step #2 about having an infinite number of list elements to be filtered out of the list. Think of it like asking a lazy child to clean the house. They're only going to do it just before mom gets home (who knows, with any luck she'll be in a car crash and forget about having asked you to clean!)

This works for infinite lists, and puts off the work until you actually need the elements.

I won't cheat you out of the fun, but here's the solution to a *very* similar problem using the Sieve of Eratosthenes to find prime numbers:

isNotDivisor divisor dividend = dividend `rem` divisor /= 0

keepOnlyLowestMultiple (x:xs) = x : keepOnlyLowestMultiple (filter (isNotDivisor x) xs)

primes = keepOnlyLowestMultiple [2..]

Dan

...
...
The problem with your second implementation is that elements which occur more than once will eventually be included, when the part of the list remaining only has one copy. For example:

unique2 [1,1,2,4,1] = unique2 [1,2,4,1] = unique2 [2,4,1] = 2 : unique2 [4,1] = 2 : 4 : unique2 [1] = 2 : 4 : 1 : unique2 [] -- only a single 1 left, so it gets mistakenly included = [2,4,1]

When you determine that a certain number should not be included in the output, you need to delete all remaining occurrences of it from the

Brent Yorgey wrote: list,

...
so it won't get included later.

unique2 (x:xs) |elemNum2 x xs == 1 = x:unique2 xs |otherwise = unique2 (deleteElt x xs)

I'll let you figure out how to implement the deleteElt function.

hope this is helpful! -Brent

On 7/10/07, Alexteslin wrote:

...
Hi, i am a beginner to Haskell and i have a beginner's question to

ask.

...
An exercise asks to define function unique :: [Int] -> [Int], which outputs a list with only elements that are unique to the input list (that

appears

...
no more than once). I defined a function with list comprehension which works but trying to implement with pattern matching and primitive recursion with lists and doesn't work.

unique :: [Int] -> [Int] unique xs = [x | x <- xs, elemNum2 x xs == 1]

elemNum2 :: Int -> [Int] -> Int elemNum2 el xs = length [x| x <- xs, x == el]

//This doesn't work, I know because the list shrinks and produces wrong result but can not get a right //thinking

unique2 :: [Int] -> [Int] unique2 [] = [] unique2 (x:xs) |elemNum2 x xs == 1 = x:unique2 xs |otherwise = unique2 xs

Any help to a right direction would be very appreciated, thanks. -- View this message in context: http://www.nabble.com/function-unique-tf4058328.html#a11528933 Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

Hugh Perkins

4:33 p.m.

Oh, lol because I'm stupid and put the arguments the wrong way around in the first recursive call to testunique' ;-) On 7/11/07, Hugh Perkins wrote:

...

Ok so I played with the tweaked problem (Unix 'uniq'), and getting it to be lazy. This seems to work:

testunique :: Eq a => [a] -> [a] testunique list = testunique' list [] where testunique' :: Eq a => [a] -> [a] -> [a] testunique' [] elementssofar = [] testunique' (x:xs) elementssofar | x `elem` elementssofar = (testunique' elementssofar xs) | otherwise = x : ( testunique' xs (x:elementssofar))

Now, a question, why is this happening:

doesnt block:

take 10 (testunique ([1,3] ++ [7..])) take 10 (testunique ([7..] ++ [1,3,7]))

blocks forever:

take 10 (testunique ([1,3,7] ++ [7..]))

The expression ([1,3,7] ++ [7..]) itself doesnt block: things like "take 10 ( [1,3,7] ++ [7 ..] )" work just fine, so what is going on?

On 7/11/07, Dan Weston wrote:

...
Alexteslin wrote:

...
I'v got it - it produces the right output. Thank you.

Now that you've done the exercise, the fun starts! What assumptions did you build in to your solution?

1) You just need uniqueness, so counting the number of copies is not only overkill, but requires you to go through the entire list to count them.

2) The list might be infinite, and your function should work if you make only want to use the first part of it, so the following should return [1,2,3,4,5] in a finite amount of time:

take 5 (unique [1..])

Your algorithm fails both of these. Consider a *lazy* approach:

1) Keep the head of the list 2) Then filter the tail, keeping only elements different from the head 3) Then put the two together

Don't worry in step #2 about having an infinite number of list elements to be filtered out of the list. Think of it like asking a lazy child to clean the house. They're only going to do it just before mom gets home (who knows, with any luck she'll be in a car crash and forget about having asked you to clean!)

This works for infinite lists, and puts off the work until you actually need the elements.

I won't cheat you out of the fun, but here's the solution to a *very* similar problem using the Sieve of Eratosthenes to find prime numbers:

isNotDivisor divisor dividend = dividend `rem` divisor /= 0

keepOnlyLowestMultiple (x:xs) = x : keepOnlyLowestMultiple (filter (isNotDivisor x) xs)

primes = keepOnlyLowestMultiple [2..]

Dan

...
Brent Yorgey wrote:

...
The problem with your second implementation is that elements which occur more than once will eventually be included, when the part of the list

...
...
remaining only has one copy. For example:

unique2 [1,1,2,4,1] = unique2 [1,2,4,1] = unique2 [2,4,1] = 2 : unique2 [4,1] = 2 : 4 : unique2 [1] = 2 : 4 : 1 : unique2 [] -- only a single 1 left, so it gets mistakenly included = [2,4,1]

When you determine that a certain number should not be included in the output, you need to delete all remaining occurrences of it from the list, so it won't get included later.

unique2 (x:xs) |elemNum2 x xs == 1 = x:unique2 xs |otherwise = unique2 (deleteElt x xs)

I'll let you figure out how to implement the deleteElt function.

hope this is helpful! -Brent

On 7/10/07, Alexteslin wrote:

...
Hi, i am a beginner to Haskell and i have a beginner's question to

ask.

...
An exercise asks to define function unique :: [Int] -> [Int], which outputs a list with only elements that are unique to the input list (that

appears

...
no more than once). I defined a function with list comprehension which works but trying to implement with pattern matching and primitive recursion with lists and doesn't work.

unique :: [Int] -> [Int] unique xs = [x | x <- xs, elemNum2 x xs == 1]

elemNum2 :: Int -> [Int] -> Int elemNum2 el xs = length [x| x <- xs, x == el]

//This doesn't work, I know because the list shrinks and produces wrong result but can not get a right //thinking

unique2 :: [Int] -> [Int] unique2 [] = [] unique2 (x:xs) |elemNum2 x xs == 1 = x:unique2 xs |otherwise = unique2 xs

Any help to a right direction would be very appreciated, thanks. -- View this message in context: http://www.nabble.com/function-unique-tf4058328.html#a11528933 Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

Hugh Perkins

4:39 p.m.

By the way, this is something that is hard in Haskell compared to say C#. In C#, when you call a function you type "(" and instantly you get a popup box telling you what the name of the first argument is, then when you've written the first argument and hit "," you get the name (and type) of the second argument. It's pretty hard not to put the right arguments in the right order. Not so in Haskell where I spend insane amounts of time trying to remember what argument is what in a function I wrote 30 seconds ago. On 7/11/07, Hugh Perkins wrote:

...

Oh, lol because I'm stupid and put the arguments the wrong way around in the first recursive call to testunique' ;-)

On 7/11/07, Hugh Perkins < hughperkins@gmail.com> wrote:

...
Ok so I played with the tweaked problem (Unix 'uniq'), and getting it to be lazy. This seems to work:

testunique :: Eq a => [a] -> [a] testunique list = testunique' list [] where testunique' :: Eq a => [a] -> [a] -> [a] testunique' [] elementssofar = [] testunique' (x:xs) elementssofar | x `elem` elementssofar = (testunique' elementssofar xs) | otherwise = x : ( testunique' xs (x:elementssofar))

Now, a question, why is this happening:

doesnt block:

take 10 (testunique ([1,3] ++ [7..])) take 10 (testunique ([7..] ++ [1,3,7]))

blocks forever:

take 10 (testunique ([1,3,7] ++ [7..]))

The expression ([1,3,7] ++ [7..]) itself doesnt block: things like "take 10 ( [1,3,7] ++ [7 ..] )" work just fine, so what is going on?

On 7/11/07, Dan Weston wrote:

...
Alexteslin wrote:

...
I'v got it - it produces the right output. Thank you.

Now that you've done the exercise, the fun starts! What assumptions did you build in to your solution?

1) You just need uniqueness, so counting the number of copies is not only overkill, but requires you to go through the entire list to count them.

2) The list might be infinite, and your function should work if you make only want to use the first part of it, so the following should return [1,2,3,4,5] in a finite amount of time:

take 5 (unique [1..])

Your algorithm fails both of these. Consider a *lazy* approach:

1) Keep the head of the list 2) Then filter the tail, keeping only elements different from the head

3) Then put the two together

Don't worry in step #2 about having an infinite number of list elements to be filtered out of the list. Think of it like asking a lazy child to clean the house. They're only going to do it just before mom gets home

(who knows, with any luck she'll be in a car crash and forget about having asked you to clean!)

This works for infinite lists, and puts off the work until you actually need the elements.

I won't cheat you out of the fun, but here's the solution to a *very* similar problem using the Sieve of Eratosthenes to find prime numbers:

isNotDivisor divisor dividend = dividend `rem` divisor /= 0

keepOnlyLowestMultiple (x:xs) = x : keepOnlyLowestMultiple (filter (isNotDivisor x) xs)

primes = keepOnlyLowestMultiple [2..]

Dan

...
...
The problem with your second implementation is that elements which occur more than once will eventually be included, when the part of the

...
remaining only has one copy. For example:

unique2 [1,1,2,4,1] = unique2 [1,2,4,1] = unique2 [2,4,1] = 2 : unique2 [4,1] = 2 : 4 : unique2 [1] = 2 : 4 : 1 : unique2 [] -- only a single 1 left, so it gets mistakenly included = [2,4,1]

When you determine that a certain number should not be included in

...
output, you need to delete all remaining occurrences of it from the

Brent Yorgey wrote: list the list,

...
so it won't get included later.

unique2 (x:xs) |elemNum2 x xs == 1 = x:unique2 xs |otherwise = unique2 (deleteElt x xs)

I'll let you figure out how to implement the deleteElt function.

hope this is helpful! -Brent

On 7/10/07, Alexteslin wrote:

...
Hi, i am a beginner to Haskell and i have a beginner's question to

ask.

...
An exercise asks to define function unique :: [Int] -> [Int],

which

...
outputs a list with only elements that are unique to the input list (that appears no more than once). I defined a function with list comprehension which works but trying to implement with pattern matching and primitive recursion with lists and doesn't work.

unique :: [Int] -> [Int] unique xs = [x | x <- xs, elemNum2 x xs == 1]

elemNum2 :: Int -> [Int] -> Int elemNum2 el xs = length [x| x <- xs, x == el]

//This doesn't work, I know because the list shrinks and produces wrong result but can not get a right //thinking

unique2 :: [Int] -> [Int] unique2 [] = [] unique2 (x:xs) |elemNum2 x xs == 1 = x:unique2 xs |otherwise = unique2 xs

Any help to a right direction would be very appreciated, thanks. -- View this message in context: http://www.nabble.com/function-unique-tf4058328.html#a11528933 Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

Andrew Coppin

4:42 p.m.

Hugh Perkins wrote:

...

By the way, this is something that is hard in Haskell compared to say C#.

In C#, when you call a function you type "(" and instantly you get a popup box telling you what the name of the first argument is, then when you've written the first argument and hit "," you get the name (and type) of the second argument.

It's pretty hard not to put the right arguments in the right order.

Not so in Haskell where I spend insane amounts of time trying to remember what argument is what in a function I wrote 30 seconds ago.

Good point! Hmm... sounds kind of hard to do in Haskell. I mean, the function might be curried. ;-) Still, you'd think it's doable.

Steve Schafer

4:42 p.m.

On Wed, 11 Jul 2007 22:39:27 +0200, you wrote:

...

In C#, when you call a function you type "(" and instantly you get a popup box telling you what the name of the first argument is, then when you've written the first argument and hit "," you get the name (and type) of the second argument.

That's not a feature of C# itself, but rather a feature of the development environment you're using. You can write C# code in NotePad, and I will guarantee you that you won't see any such popups. ;) There do exist various development environments for Haskell, but I don't think any of them are particularly popular. Steve Schafer Fenestra Technologies Corp. http://www.fenestra.com/

Hugh Perkins

4:49 p.m.

Well, there's a fundamental reason it wont work for Haskell: we dont actually define the names of the parameters to the function! Have a look at the function above, the function is defined as: testunique' :: Eq a => [a] -> [a] -> [a] testunique' [] elementssofar = [] testunique' (x:xs) elementssofar There's an agreement here that the second parameter is called "elementssofar"... but only because I was consistent in my naming in this example. What if we had multiple constructors for a particular type? The first argument has no obvious naming at all. We could do things like write it in comments: testunique' :: Eq a => [a] -> [a] -> [a] -- testunique' :: remainingelements -> elementssofar -> uniqueelements testunique' [] elementssofar = [] testunique' (x:xs) elementssofar ... but we all know that no-one bothers writing comments, and certainly never maintaining them, and in any case this is becoming insanely difficult to read. I dont have a solution, apart from using C# for production programming ;-) , but things like this are really important to solve in any "mainstream" version of Haskell. On 7/11/07, Steve Schafer wrote:

...

On Wed, 11 Jul 2007 22:39:27 +0200, you wrote:

...
In C#, when you call a function you type "(" and instantly you get a popup box telling you what the name of the first argument is, then when you've written the first argument and hit "," you get the name (and type) of the second argument.

That's not a feature of C# itself, but rather a feature of the development environment you're using. You can write C# code in NotePad, and I will guarantee you that you won't see any such popups. ;)

There do exist various development environments for Haskell, but I don't think any of them are particularly popular.

Steve Schafer Fenestra Technologies Corp. http://www.fenestra.com/ _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

Jonathan Cast

4:59 p.m.

On Wednesday 11 July 2007, Hugh Perkins wrote:

...

Well, there's a fundamental reason it wont work for Haskell: we dont actually define the names of the parameters to the function!

Have a look at the function above, the function is defined as:

testunique' :: Eq a => [a] -> [a] -> [a] testunique' [] elementssofar = [] testunique' (x:xs) elementssofar

There's an agreement here that the second parameter is called "elementssofar"... but only because I was consistent in my naming in this example. What if we had multiple constructors for a particular type?

The first argument has no obvious naming at all.

We could do things like write it in comments:

testunique' :: Eq a => [a] -> [a] -> [a] -- testunique' :: remainingelements -> elementssofar -> uniqueelements testunique' [] elementssofar = [] testunique' (x:xs) elementssofar

... but we all know that no-one bothers writing comments, and certainly never maintaining them, and in any case this is becoming insanely difficult to read.

I dont have a solution, apart from using C# for production programming ;-) , but things like this are really important to solve in any "mainstream" version of Haskell.

One could put up the Haddock doc-comment. Or, say, one could extend Haddock to support parameter names: testunique' :: Eq a => [a] -- ^ $list List of elements to test -> [a] -- ^ $elementssofar List of elements seen thus far -> [a] -- ^ List of unique elements in 'list'. No patch forthcoming from this corner, though. Jonathan Cast http://sourceforge.net/projects/fid-core http://sourceforge.net/projects/fid-emacs

Stefan O'Rear

5:06 p.m.

On Wed, Jul 11, 2007 at 03:59:45PM -0500, Jonathan Cast wrote:

...

One could put up the Haddock doc-comment. Or, say, one could extend Haddock to support parameter names:

testunique' :: Eq a => [a] -- ^ $list List of elements to test -> [a] -- ^ $elementssofar List of elements seen thus far -> [a] -- ^ List of unique elements in 'list'.

No patch forthcoming from this corner, though.

None necessary! Haddock already supports that syntax. http://haskell.org/haddock/haddock-html-0.8/ch03s02.html#id289091 Stefan

Jonathan Cast

5:33 p.m.

On Wednesday 11 July 2007, you wrote:

...

On Wed, Jul 11, 2007 at 03:59:45PM -0500, Jonathan Cast wrote:

...
One could put up the Haddock doc-comment. Or, say, one could extend Haddock to support parameter names:

testunique' :: Eq a => [a] -- ^ $list List of elements to test -> [a] -- ^ $elementssofar List of elements seen thus far -> [a] -- ^ List of unique elements in 'list'.

No patch forthcoming from this corner, though.

None necessary! Haddock already supports that syntax.

http://haskell.org/haddock/haddock-html-0.8/ch03s02.html#id289091

I think you missed my overloading of the section-label syntax to get argument names. And it's not even quite supported; trying the example gets you $ haddock -h Foo.hs Warning: Foo: the following names could not be resolved: Eq list Jonathan Cast http://sourceforge.net/projects/fid-core http://sourceforge.net/projects/fid-emacs

Stefan O'Rear

5:39 p.m.

On Wed, Jul 11, 2007 at 04:33:19PM -0500, Jonathan Cast wrote:

...

On Wednesday 11 July 2007, you wrote:

...
On Wed, Jul 11, 2007 at 03:59:45PM -0500, Jonathan Cast wrote:

...
One could put up the Haddock doc-comment. Or, say, one could extend Haddock to support parameter names:

testunique' :: Eq a => [a] -- ^ $list List of elements to test -> [a] -- ^ $elementssofar List of elements seen thus far -> [a] -- ^ List of unique elements in 'list'.

No patch forthcoming from this corner, though.

None necessary! Haddock already supports that syntax.

http://haskell.org/haddock/haddock-html-0.8/ch03s02.html#id289091

I think you missed my overloading of the section-label syntax to get argument names.

Indeed.

...

And it's not even quite supported; trying the example gets you

$ haddock -h Foo.hs Warning: Foo: the following names could not be resolved: Eq list

Uhm... that's a *successful* run. I think you meant to copy the messages from a failed run? Stefan

Steve Schafer

5:27 p.m.

On Wed, 11 Jul 2007 22:49:27 +0200, you wrote:

...

Well, there's a fundamental reason it wont work for Haskell: we dont actually define the names of the parameters to the function!

Yes, but you know the type, which is what really counts. And, taking that a step further, once you've entered something for the first argument, a real-time compiler might be able to narrow down the set of allowed types for the second argument, and so on. Of course, if you're in the habit of creating functions with type signatures like Int -> Int -> Int -> Int -> Int -> Int, and you can't remember which Int does what, then you have only yourself to blame.... Steve Schafer Fenestra Technologies Corp. http://www.fenestra.com/

Henning Thielemann

12 Jul 12 Jul

4:19 a.m.

New subject: IDE for Haskell (Was: function unique)

On Wed, 11 Jul 2007, Steve Schafer wrote:

...

On Wed, 11 Jul 2007 22:39:27 +0200, you wrote:

...
In C#, when you call a function you type "(" and instantly you get a popup box telling you what the name of the first argument is, then when you've written the first argument and hit "," you get the name (and type) of the second argument.

That's not a feature of C# itself, but rather a feature of the development environment you're using. You can write C# code in NotePad, and I will guarantee you that you won't see any such popups. ;)

There do exist various development environments for Haskell, but I don't think any of them are particularly popular.

Since you can write Plugins for Eclipse in Haskell, things become interesting: http://leiffrenzel.de/eclipse/cohatoe/

Albert Y. C. Lai

13 Jul 13 Jul

4:28 p.m.

New subject: IDE for Haskell (Was: function unique)

Henning Thielemann wrote:

...

Since you can write Plugins for Eclipse in Haskell, things become interesting: http://leiffrenzel.de/eclipse/cohatoe/

Yippee! I have added an entry for it to http://www.haskell.org/haskellwiki/Applications_and_libraries/Editors

Philip Armstrong

12 Jul 12 Jul

5:18 p.m.

On Wed, Jul 11, 2007 at 10:31:36PM +0200, Hugh Perkins wrote:

...

Ok so I played with the tweaked problem (Unix 'uniq'), and getting it to be lazy. This seems to work:

It's slightly worse than that: unix uniq only eliminates *consecutive* identical lines from its input. If you want to eliminate all duplicates, you have to pipe your input through sort first.

...

testunique :: Eq a => [a] -> [a] testunique list = testunique' list [] where testunique' :: Eq a => [a] -> [a] -> [a] testunique' [] elementssofar = [] testunique' (x:xs) elementssofar | x `elem` elementssofar = (testunique' elementssofar xs) | otherwise = x : ( testunique' xs (x:elementssofar))

I suspect the author upthread had something more like this in mind: uniq :: Eq a => [a] -> [a] uniq [] = [] uniq (x:xs) = x : filter (x/=) (uniq2 xs) Obviously a true 'unique' function has to traverse the entire list before it creates any output, as has been pointed out upthread. Phil -- http://www.kantaka.co.uk/ .oOo. public key: http://www.kantaka.co.uk/gpg.txt

Dan Weston

5:33 p.m.

Philip Armstrong wrote:

...

On Wed, Jul 11, 2007 at 10:31:36PM +0200, Hugh Perkins wrote:

...
Ok so I played with the tweaked problem (Unix 'uniq'), and getting it to be lazy. This seems to work:

It's slightly worse than that: unix uniq only eliminates *consecutive* identical lines from its input. If you want to eliminate all duplicates, you have to pipe your input through sort first.

...
testunique :: Eq a => [a] -> [a] testunique list = testunique' list [] where testunique' :: Eq a => [a] -> [a] -> [a] testunique' [] elementssofar = [] testunique' (x:xs) elementssofar | x `elem` elementssofar = (testunique' elementssofar xs) | otherwise = x : ( testunique' xs (x:elementssofar))

I suspect the author upthread had something more like this in mind:

uniq :: Eq a => [a] -> [a] uniq [] = [] uniq (x:xs) = x : filter (x/=) (uniq2 xs)

Obviously a true 'unique' function has to traverse the entire list before it creates any output, as has been pointed out upthread.

Phil

Close. Actually, the author upstream (i.e. me) had in mind:

...

uniq :: Eq a => [a] -> [a] uniq [] = [] uniq (x:xs) = x : uniq (filter (/= x) xs)

Dan Weston

5:37 p.m.

Now that I mention it, the base case is much less often called than the recursive case, so I would in hindsight flip the order of the two (mutually exclusive) partial function definitions: unique :: Eq a => [a] -> [a] unique (x:xs) = x : (unique . filter (/= x) $ xs) unique [] = [] This should be marginally more efficient. I doubt that GHC would automatically detect that a) they are mutually exclusive and b) the second is called less often than the first! Dan Dan Weston wrote:

...

Close. Actually, the author upstream (i.e. me) had in mind:

...
uniq :: Eq a => [a] -> [a] uniq [] = [] uniq (x:xs) = x : uniq (filter (/= x) xs)

Dan Weston

5:41 p.m.

While we're at it, the second pattern match is superfluous. Once you take out nonempty lists from the list type, the only thing left is an empty one! unique :: Eq a => [a] -> [a] unique (x:xs) = x : (unique . filter (/= x) $ xs) unique _ = [] One question left: would the second definition be more efficient if written: unique e = e Inquiring minds want to know... Dan Dan Weston wrote:

...

Now that I mention it, the base case is much less often called than the recursive case, so I would in hindsight flip the order of the two (mutually exclusive) partial function definitions:

unique :: Eq a => [a] -> [a] unique (x:xs) = x : (unique . filter (/= x) $ xs) unique [] = []

This should be marginally more efficient. I doubt that GHC would automatically detect that a) they are mutually exclusive and b) the second is called less often than the first!

Dan

Dan Weston wrote:

...
Close. Actually, the author upstream (i.e. me) had in mind:

...
uniq :: Eq a => [a] -> [a] uniq [] = [] uniq (x:xs) = x : uniq (filter (/= x) xs)

Jonathan Cast

5:53 p.m.

On Thursday 12 July 2007, Dan Weston wrote:

...

While we're at it, the second pattern match is superfluous. Once you take out nonempty lists from the list type, the only thing left is an empty one!

unique :: Eq a => [a] -> [a] unique (x:xs) = x : (unique . filter (/= x) $ xs) unique _ = []

One question left: would the second definition be more efficient if written:

unique e = e

Inquiring minds want to know...

No. Of course not. Before making wild guesses about how GHC is implementing your code, read (and understand[1]) the STG paper: http://research.microsoft.com/copyright/accept.asp?path=/users/simonpj/papers/spineless-tagless-gmachine.ps.gz&pub=34 And then as many as you can of the other papers available here. http://research.microsoft.com/~simonpj/Papers/papers.html To answer your question: [] is treated like a variable, except it's a variable whose behavior is statically known, so the compiler can do more with it. In fact, all of your versions given are equivalent in GHC, but only because you're taking advantage of more and more of the heroic work GHC does to convert your later versions into your earlier ones. Jonathan Cast http://sourceforge.net/projects/fid-core http://sourceforge.net/projects/fid-emacs [1] Understanding the STG paper is not a requirement to using Haskell, just to making wild (incorrect) guesses about how the compiler's going to treat your code. But, of course, making wild (incorrect) guesses about how the compiler's going to treat your code is not a requirement to using Haskell.

Tim Chevalier

5:59 p.m.

On 7/12/07, Jonathan Cast wrote:

...

No. Of course not. Before making wild guesses about how GHC is implementing your code, read (and understand[1]) the STG paper:

http://research.microsoft.com/copyright/accept.asp?path=/users/simonpj/papers/spineless-tagless-gmachine.ps.gz&pub=34

In this particular case, reading the simplifier paper would probably be more relevant: http://research.microsoft.com/copyright/accept.asp?path=/users/simonpj/papers/comp-by-trans.ps.gz&pub=18 Or even just understanding the syntax of Core, really.

...

[1] Understanding the STG paper is not a requirement to using Haskell, just to making wild (incorrect) guesses about how the compiler's going to treat your code. But, of course, making wild (incorrect) guesses about how the compiler's going to treat your code is not a requirement to using Haskell.

Amen! Cheers, Tim -- Tim Chevalier* catamorphism.org *Often in error, never in doubt "Everyone's too stupid." -- _Ghost World_

Dan Weston

6:19 p.m.

Tim Chevalier wrote:

...

On 7/12/07, Jonathan Cast wrote:

...
No. Of course not. Before making wild guesses about how GHC is implementing your code, read (and understand[1]) the STG paper:

http://research.microsoft.com/copyright/accept.asp?path=/users/simonpj/papers/spineless-tagless-gmachine.ps.gz&pub=34

In this particular case, reading the simplifier paper would probably be more relevant: http://research.microsoft.com/copyright/accept.asp?path=/users/simonpj/papers/comp-by-trans.ps.gz&pub=18

Or even just understanding the syntax of Core, really.

...
[1] Understanding the STG paper is not a requirement to using Haskell, just to making wild (incorrect) guesses about how the compiler's going to treat your code. But, of course, making wild (incorrect) guesses about how the compiler's going to treat your code is not a requirement to using Haskell.

Amen!

Cheers, Tim

I realize now that it was inappropriate to pose a question to this list before I knew the answer! :( Anyway, it turned out that the two ghc -ddump-simpl outputs were in fact identical, but only after identifier renaming. It would be very useful to have a tool that takes two core files and attempts to rename identifiers from the second to match the first. Is there already such a smart-diff tool out there? Dan

Jonathan Cast

5:47 p.m.

On Thursday 12 July 2007, Dan Weston wrote:

...

Now that I mention it, the base case is much less often called than the recursive case, so I would in hindsight flip the order of the two (mutually exclusive) partial function definitions:

unique :: Eq a => [a] -> [a] unique (x:xs) = x : (unique . filter (/= x) $ xs) unique [] = []

This should be marginally more efficient. I doubt that GHC would automatically detect that a) they are mutually exclusive and b) the second is called less often than the first!

Actually, it would (well, sort of). GHC expends a good deal of effort looking for cases where pattern-matching is mutually-exclusive, and flattens it out to unique xn' = case xn' of [] -> [] x : xn -> x : unique (filter (/= x) xn) where each branch is equally efficient. Jonathan Cast http://sourceforge.net/projects/fid-core http://sourceforge.net/projects/fid-emacs

Tim Chevalier

5:49 p.m.

On 7/12/07, Dan Weston wrote:

...

Now that I mention it, the base case is much less often called than the recursive case, so I would in hindsight flip the order of the two (mutually exclusive) partial function definitions:

unique :: Eq a => [a] -> [a] unique (x:xs) = x : (unique . filter (/= x) $ xs) unique [] = []

This should be marginally more efficient. I doubt that GHC would automatically detect that a) they are mutually exclusive and b) the second is called less often than the first!

Of course GHC detects that the cases are mutually exclusive. The code above desugars into a single definition of unique with a case expression on its argument. In Core, case expressions have at most one alternative for each data constructor of the type of the scrutinee, and since each alternative corresponds to a different top-level data constructor, alternatives are mutually exclusive. As for point (b), it hardly matters, since GHC will rearrange case alternatives at will (and I don't think the order of alternatives has any operational meaning anyway.) If you want to see this for yourself, try running GHC with the -ddump-simpl flag on a simple example (like the one above). Cheers, Tim -- Tim Chevalier* catamorphism.org *Often in error, never in doubt "What doesn't kill you, makes you stronger -- or puts you on a talk show." --Carrie Fisher

6526

Age (days ago)

6529

Last active (days ago)

List overview

Download

33 comments

14 participants

participants (14)

Albert Y. C. Lai
Alexteslin
Andrew Coppin
Antoine Latter
Brent Yorgey
Dan Weston
Henning Thielemann
Hugh Perkins
Jonathan Cast
Neil Mitchell
Philip Armstrong
Stefan O'Rear
Steve Schafer
Tim Chevalier

function unique

Hugh Perkins

Hugh Perkins

Hugh Perkins

Hugh Perkins

Andrew Coppin

Steve Schafer

Hugh Perkins

Steve Schafer

Philip Armstrong

Tim Chevalier

Tim Chevalier

tags

participants (14)