How can I determine if a function is being memoized in Haskell?

I've got a Haskell program that is performing non linearly performance wise (worse then O(n)).

I'm trying to investigate whether memoization is taking place on a function, can I verify this? I'm familiar with GHC profiling - but I'm not too sure which values I should be looking at?

A work around is too just plug some values and observe the execution time - but it's not ideal.

edited Jan 2 at 19:57

chepner

258k34249343

asked Jan 2 at 10:48

Chris Stryczynski

4,38353276

kseo.github.io/posts/2017-01-14-memoization-in-hasekll.html

– Thomas Cook
Jan 2 at 10:53

wiki.haskell.org/Memoization

– Thomas Cook
Jan 2 at 10:54

4

You can read the Core output by GHC (with ghc -ddump-simpl -dsuppress-all), and look for let bindings that should be floated out of their surrounding functions.

– Li-yao Xia
Jan 2 at 12:46

1

Care to share a code snippet? Or wouldn that be distracting to us? Curious what it is about.

– Elmex80s
Jan 2 at 19:38

1

Use Debug.Trace on things you think might be recomputed, see if they show up multiple times

– luqui
Jan 3 at 6:35

|
show 2 more comments

I've got a Haskell program that is performing non linearly performance wise (worse then O(n)).

I'm trying to investigate whether memoization is taking place on a function, can I verify this? I'm familiar with GHC profiling - but I'm not too sure which values I should be looking at?

A work around is too just plug some values and observe the execution time - but it's not ideal.

edited Jan 2 at 19:57

chepner

258k34249343

asked Jan 2 at 10:48

Chris Stryczynski

4,38353276

kseo.github.io/posts/2017-01-14-memoization-in-hasekll.html

– Thomas Cook
Jan 2 at 10:53

wiki.haskell.org/Memoization

– Thomas Cook
Jan 2 at 10:54

4

You can read the Core output by GHC (with ghc -ddump-simpl -dsuppress-all), and look for let bindings that should be floated out of their surrounding functions.

– Li-yao Xia
Jan 2 at 12:46

1

Care to share a code snippet? Or wouldn that be distracting to us? Curious what it is about.

– Elmex80s
Jan 2 at 19:38

1

Use Debug.Trace on things you think might be recomputed, see if they show up multiple times

– luqui
Jan 3 at 6:35

|
show 2 more comments

I've got a Haskell program that is performing non linearly performance wise (worse then O(n)).

I'm trying to investigate whether memoization is taking place on a function, can I verify this? I'm familiar with GHC profiling - but I'm not too sure which values I should be looking at?

A work around is too just plug some values and observe the execution time - but it's not ideal.

edited Jan 2 at 19:57

chepner

258k34249343

asked Jan 2 at 10:48

Chris Stryczynski

4,38353276

I've got a Haskell program that is performing non linearly performance wise (worse then O(n)).

I'm trying to investigate whether memoization is taking place on a function, can I verify this? I'm familiar with GHC profiling - but I'm not too sure which values I should be looking at?

A work around is too just plug some values and observe the execution time - but it's not ideal.

haskell memoization

edited Jan 2 at 19:57

chepner

258k34249343

asked Jan 2 at 10:48

Chris Stryczynski

4,38353276

edited Jan 2 at 19:57

chepner

258k34249343

asked Jan 2 at 10:48

Chris Stryczynski

4,38353276

edited Jan 2 at 19:57

chepner

258k34249343

edited Jan 2 at 19:57

chepner

258k34249343

edited Jan 2 at 19:57

chepner

258k34249343

asked Jan 2 at 10:48

Chris Stryczynski

4,38353276

asked Jan 2 at 10:48

Chris Stryczynski

4,38353276

asked Jan 2 at 10:48

Chris Stryczynski

4,38353276

kseo.github.io/posts/2017-01-14-memoization-in-hasekll.html

– Thomas Cook
Jan 2 at 10:53

wiki.haskell.org/Memoization

– Thomas Cook
Jan 2 at 10:54

4

You can read the Core output by GHC (with ghc -ddump-simpl -dsuppress-all), and look for let bindings that should be floated out of their surrounding functions.

– Li-yao Xia
Jan 2 at 12:46

1

Care to share a code snippet? Or wouldn that be distracting to us? Curious what it is about.

– Elmex80s
Jan 2 at 19:38

1

Use Debug.Trace on things you think might be recomputed, see if they show up multiple times

– luqui
Jan 3 at 6:35

|
show 2 more comments

kseo.github.io/posts/2017-01-14-memoization-in-hasekll.html

– Thomas Cook
Jan 2 at 10:53

wiki.haskell.org/Memoization

– Thomas Cook
Jan 2 at 10:54

4

You can read the Core output by GHC (with ghc -ddump-simpl -dsuppress-all), and look for let bindings that should be floated out of their surrounding functions.

– Li-yao Xia
Jan 2 at 12:46

1

Care to share a code snippet? Or wouldn that be distracting to us? Curious what it is about.

– Elmex80s
Jan 2 at 19:38

1

Use Debug.Trace on things you think might be recomputed, see if they show up multiple times

– luqui
Jan 3 at 6:35

kseo.github.io/posts/2017-01-14-memoization-in-hasekll.html

– Thomas Cook
Jan 2 at 10:53

wiki.haskell.org/Memoization

– Thomas Cook
Jan 2 at 10:54

You can read the Core output by GHC (with ghc -ddump-simpl -dsuppress-all), and look for let bindings that should be floated out of their surrounding functions.

– Li-yao Xia
Jan 2 at 12:46

Care to share a code snippet? Or wouldn that be distracting to us? Curious what it is about.

– Elmex80s
Jan 2 at 19:38

Use Debug.Trace on things you think might be recomputed, see if they show up multiple times

– luqui
Jan 3 at 6:35

|
show 2 more comments

1 Answer
1

active

oldest

votes

As far as I know there is no automatic memoization in Haskell.

That said there seems to be an optimization in GHC that caches values for parameterless function like the following

rightTriangles = [ (a,b,c) | 

    c <- [1..], 

    b <- [1..c], 

    a <- [1..b], 

    a^2 + b^2 == c^2]

If you try out the following in GHCi twice, you'll see that the second call ist much faster:

ghci > take 500 rightTriangles

answered Jan 2 at 11:36

Thomas Mahler

687

7

There is no such thing as "parameterless functions" in Haskell. rightTriangles is just a list. Laziness means the individual values in the list are only computed on demand. When you first call take 500 rightTriangles, the first 500 values have to actually be computed (in order to actually display the values). For the second call, those first 500 values are, of course, still in memory.

– chepner
Jan 2 at 14:02

1

yes, if by "parameterless functions" you mean "constant applicative forms" or CAFs.

– Will Ness
Jan 2 at 22:32

yes, I was taking about CAFs. ints = from 1 where from n = n : from (n+1) is another example for a CAF.

– Thomas Mahler
Jan 3 at 15:15

add a comment |

Your Answer

StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});

}
});

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f54004969%2fhow-can-i-determine-if-a-function-is-being-memoized-in-haskell%23new-answer', 'question_page');
}
);

Post as a guest

Name

Required, but never shown

1 Answer
1

active

oldest

votes

1 Answer
1

active

oldest

votes

As far as I know there is no automatic memoization in Haskell.

That said there seems to be an optimization in GHC that caches values for parameterless function like the following

rightTriangles = [ (a,b,c) | 

    c <- [1..], 

    b <- [1..c], 

    a <- [1..b], 

    a^2 + b^2 == c^2]

If you try out the following in GHCi twice, you'll see that the second call ist much faster:

ghci > take 500 rightTriangles

answered Jan 2 at 11:36

Thomas Mahler

687

7

There is no such thing as "parameterless functions" in Haskell. rightTriangles is just a list. Laziness means the individual values in the list are only computed on demand. When you first call take 500 rightTriangles, the first 500 values have to actually be computed (in order to actually display the values). For the second call, those first 500 values are, of course, still in memory.

– chepner
Jan 2 at 14:02

1

yes, if by "parameterless functions" you mean "constant applicative forms" or CAFs.

– Will Ness
Jan 2 at 22:32

yes, I was taking about CAFs. ints = from 1 where from n = n : from (n+1) is another example for a CAF.

– Thomas Mahler
Jan 3 at 15:15

add a comment |

As far as I know there is no automatic memoization in Haskell.

That said there seems to be an optimization in GHC that caches values for parameterless function like the following

rightTriangles = [ (a,b,c) | 

    c <- [1..], 

    b <- [1..c], 

    a <- [1..b], 

    a^2 + b^2 == c^2]

If you try out the following in GHCi twice, you'll see that the second call ist much faster:

ghci > take 500 rightTriangles

answered Jan 2 at 11:36

Thomas Mahler

687

7

There is no such thing as "parameterless functions" in Haskell. rightTriangles is just a list. Laziness means the individual values in the list are only computed on demand. When you first call take 500 rightTriangles, the first 500 values have to actually be computed (in order to actually display the values). For the second call, those first 500 values are, of course, still in memory.

– chepner
Jan 2 at 14:02

1

yes, if by "parameterless functions" you mean "constant applicative forms" or CAFs.

– Will Ness
Jan 2 at 22:32

yes, I was taking about CAFs. ints = from 1 where from n = n : from (n+1) is another example for a CAF.

– Thomas Mahler
Jan 3 at 15:15

add a comment |

As far as I know there is no automatic memoization in Haskell.

That said there seems to be an optimization in GHC that caches values for parameterless function like the following

rightTriangles = [ (a,b,c) | 

    c <- [1..], 

    b <- [1..c], 

    a <- [1..b], 

    a^2 + b^2 == c^2]

If you try out the following in GHCi twice, you'll see that the second call ist much faster:

ghci > take 500 rightTriangles

answered Jan 2 at 11:36

Thomas Mahler

687

As far as I know there is no automatic memoization in Haskell.

That said there seems to be an optimization in GHC that caches values for parameterless function like the following

rightTriangles = [ (a,b,c) | 

    c <- [1..], 

    b <- [1..c], 

    a <- [1..b], 

    a^2 + b^2 == c^2]

If you try out the following in GHCi twice, you'll see that the second call ist much faster:

ghci > take 500 rightTriangles

answered Jan 2 at 11:36

Thomas Mahler

687

answered Jan 2 at 11:36

Thomas Mahler

687

answered Jan 2 at 11:36

Thomas Mahler

687

answered Jan 2 at 11:36

Thomas Mahler

687

7

There is no such thing as "parameterless functions" in Haskell. rightTriangles is just a list. Laziness means the individual values in the list are only computed on demand. When you first call take 500 rightTriangles, the first 500 values have to actually be computed (in order to actually display the values). For the second call, those first 500 values are, of course, still in memory.

– chepner
Jan 2 at 14:02

1

yes, if by "parameterless functions" you mean "constant applicative forms" or CAFs.

– Will Ness
Jan 2 at 22:32

yes, I was taking about CAFs. ints = from 1 where from n = n : from (n+1) is another example for a CAF.

– Thomas Mahler
Jan 3 at 15:15

add a comment |

7

There is no such thing as "parameterless functions" in Haskell. rightTriangles is just a list. Laziness means the individual values in the list are only computed on demand. When you first call take 500 rightTriangles, the first 500 values have to actually be computed (in order to actually display the values). For the second call, those first 500 values are, of course, still in memory.

– chepner
Jan 2 at 14:02

1

yes, if by "parameterless functions" you mean "constant applicative forms" or CAFs.

– Will Ness
Jan 2 at 22:32

yes, I was taking about CAFs. ints = from 1 where from n = n : from (n+1) is another example for a CAF.

– Thomas Mahler
Jan 3 at 15:15

There is no such thing as "parameterless functions" in Haskell. rightTriangles is just a list. Laziness means the individual values in the list are only computed on demand. When you first call take 500 rightTriangles, the first 500 values have to actually be computed (in order to actually display the values). For the second call, those first 500 values are, of course, still in memory.

– chepner
Jan 2 at 14:02

yes, if by "parameterless functions" you mean "constant applicative forms" or CAFs.

– Will Ness
Jan 2 at 22:32

yes, I was taking about CAFs. ints = from 1 where from n = n : from (n+1) is another example for a CAF.

– Thomas Mahler
Jan 3 at 15:15

add a comment |

draft saved

draft discarded

Thanks for contributing an answer to Stack Overflow!

Please be sure to answer the question. Provide details and share your research!

But avoid …

Asking for help, clarification, or responding to other answers.

Making statements based on opinion; back them up with references or personal experience.

To learn more, see our tips on writing great answers.

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Name

Required, but never shown

Name

Required, but never shown

This page is only for reference, If you need detailed information, please check here

Search This Blog

Ufyukyu